Introduction

The sliding window algorithm is generally used on problems that look for some max, min, or target value in a contiguous sequence within an array. It is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

How to identify?

• The problem will involve a data structure that is ordered and iterable like an array or a string
• You are looking for some subrange in that array/string, like a longest, shortest or target value.
• There is an apparent naive or brute force solution that runs in O(N²), O(2^N) or some other large time complexity.

But the biggest giveaway is that the thing you are looking for is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

Characteristics of the problems that can be solved by two pointers. The summary is simple:

1. If a wider scope of the sliding window is valid, the narrower scope of that wider scope is valid mush hold.
2. If a narrower scope of the sliding window is invalid, the wider scope of that narrower scope is invalid mush hold.

Approaches

The window represents the current section of the string/array that you are “looking at” and usually there is some information stored along with it in the form of constants. At the very least it will have 2 pointers, one indicating the index corresponding beginning of the window, and one indicating the end of the window.

Basic pattern:

The basic pattern which is used for questions with single array/string input, where dynamic frequency map can be calculated on the fly.

Like:

Fruits into baskets

1. Create frequency map.
2. Increment character/number frequency with end pointer.
3. Check a condition.
4. Remove element with start pointer if it's frequency is 0.