How to Implement the Sliding Window Technique

Many problems ask you to find a subarray or substring that satisfies some condition, such as the maximum sum subarray of size K or the longest substring without repeating characters. The naive approach checks every possible window which is slow. Sliding Window maintains a window of elements and slides it across the array without restarting from scratch.

There are two types of sliding windows. A fixed size window always maintains exactly K elements. A variable size window grows and shrinks based on whether the current window satisfies the given condition. Identify which type fits your problem before writing any code.

For a fixed window of size K, first process the initial window covering indices zero to K minus one. Calculate whatever value you need, such as the sum or count, for this first window. Store it as the current result.

Starting from index K, move one step at a time. Add the new element entering the window on the right. Remove the element leaving the window on the left, which is the element K positions behind the current index. Update your tracked value accordingly and check if the new window gives a better result.

For a variable window, use two pointers called LEFT and RIGHT both starting at index zero. RIGHT expands the window by moving forward one step at a time in the outer loop. After expanding, check if the current window violates the condition.

When the window violates the condition, move LEFT forward to shrink the window from the left side. Keep shrinking by incrementing LEFT until the window satisfies the condition again. Update any tracking variables like a frequency map or running sum whenever LEFT moves.

After every expansion and possible shrinking, the window between LEFT and RIGHT is valid. Update your answer by comparing the current window size or value against the best result seen so far. After the RIGHT pointer has moved through the entire array, you have your final answer.