Pattern8 min read

Sliding Window

Two pointers that move in the same direction to compute window-based answers in O(n).

arraysstringstwo-pointers

Intro

Sliding window collapses the brute-force O(n²) subarray search into O(n) by reusing the work done at the previous position. You expand the right pointer to grow the window, and shrink the left pointer when the window stops being valid.

Key insight

The window represents 'the best answer ending at index right'. Whenever validity breaks, shrink from the left until it holds again.

Approach

1Initialise left = 0 and an aggregate (sum, character counts, distinct count, …).
2Iterate right from 0 to n-1, including arr[right] in the aggregate.
3While the window is invalid, drop arr[left] from the aggregate and increment left.
4After each step, update the answer using the current window (right - left + 1).

Example

Input

s = "abcabcbb" → longest substring with all unique characters

Output

3 ("abc")

Trace

right=0..2 → window 'abc', size 3
right=3 'a' duplicates → shrink until left=1, window 'bca'
right=4 'b' duplicates → left=2, window 'cab' …
max never exceeds 3.

Complexity

Time

O(n)

Space

O(k) for the auxiliary aggregate

Code

Java — longest substring without repeatsjava

int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];
    Arrays.fill(last, -1);
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last[c] >= left) left = last[c] + 1;
        last[c] = right;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Python — minimum window sum ≥ targetpython

def min_window_sum(arr, target):
    left, total, best = 0, 0, float('inf')
    for right, x in enumerate(arr):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= arr[left]
            left += 1
    return 0 if best == float('inf') else best

Pitfalls

Forgetting to subtract the leftmost element when shrinking the window.
Using a HashMap when a 26- or 128-element array would do — slower in tight loops.
Updating the answer outside the window-valid region (off-by-one).

Variants & follow-ups

Longest substring with at most K distinct characters
Permutation in string (LC 567)
Find all anagrams in a string (LC 438)