Back to Study Material Data Structures and Algorithms

Sliding Window Technique

The sliding window technique maintains a contiguous subarray or substring of an array or string, adjusting the window boundaries as the scan progresses to ...

Sliding Window Technique

Maintaining a Moving Subarray to Solve Fixed and Variable Window Problems

The sliding window technique maintains a contiguous subarray or substring of an array or string, adjusting the window boundaries as the scan progresses to avoid redundant work. Instead of recalculating the property of every possible subarray from scratch, the window tracks how it changes as elements enter from the right and leave from the left, achieving O(n) time where a naive approach would take O(n^2) or worse.

There are two varieties: fixed-size windows and variable-size windows. Fixed-size sliding windows compute a property, such as sum or maximum, for every subarray of length k. Initialize by computing the property for the first window covering indices 0 to k minus one. Then slide: add the new right element and remove the left element that falls out of the window, updating the property incrementally. This yields O(n) time because each element is added and removed exactly once.

Variable-size windows adjust the window boundaries based on a constraint. A common problem: find the length of the shortest subarray with a sum at least S. Use two pointers, left and right, both starting at index zero. Expand the window by moving right and adding A[right] to the current sum. When the sum meets or exceeds S, record the window length and try to shrink the window by moving left right and subtracting A[left] from the sum, repeating as long as the constraint is still met. This process runs in O(n) because each pointer moves at most n steps.

The sliding window pattern relies on a key property: the problem answer exhibits monotonicity, meaning that if a window of size k satisfies the constraint, expanding it continues to satisfy it (or vice versa for minimum problems). This allows the greedy expansion-and-shrink approach to be correct.

Applications span many domains: maximum sum subarray of size k, longest substring without repeating characters, minimum window substring containing all characters of a pattern, and count of subarrays with a product less than a given value.

For the minimum window substring problem, a hash map tracks the character frequencies inside the window and compares them to the required frequencies. The window expands rightward until all required characters are present, then shrinks leftward to find the smallest such window, repeating for every valid configuration.

Worked example: find the maximum sum of any subarray of exactly k elements in an unsorted array. Compute the sum of the first k elements. Then for each subsequent position, add the next element and subtract the element k positions behind. Track the running maximum. Total time: O(n), space: O(1).

Interview tip: when a problem asks about subarrays or substrings with a length or value constraint, ask yourself whether a sliding window can maintain the relevant property incrementally. If the constraint is monotone, the answer is almost certainly yes.