Home › Sliding Window Pattern - DSA Fundamentals

Sliding Window

The pattern: Maintain a “window” (a contiguous subarray or substring) that slides across the input, expanding or shrinking to find an optimal answer — longest, shortest, or maximum/minimum something.

Why this matters in interviews: Sliding window converts brute-force O(n²) or O(n³) substring/subarray problems into O(n). It’s one of the highest-frequency patterns and often the first optimization interviewers expect you to reach for.

When to Recognize It

How It Works

Think of it like looking through a physical window on a train. As the train moves forward, new scenery appears on the right, and old scenery disappears on the left. You’re trying to find the best view (optimal window).

flowchart LR
    A["left pointer"]:::client
    B["... elements in window ..."]:::service
    C["right pointer"]:::data
    D["expand right"]:::data
    E["shrink left"]:::client

    E --> A
    A --> B
    B --> C
    C --> D

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

The two flavors:

  1. Fixed window: The window size is given (size K). Slide it one step at a time.
  2. Variable window: Expand the right pointer until the window becomes invalid, then shrink from the left until it’s valid again. Track the best answer along the way.

Template Code

Code

def sliding_window(s, k):
    """Variable-size sliding window template."""
    left = 0
    best = 0
    window_state = {}  # track frequencies, sum, etc.

    for right in range(len(s)):
        # 1. Expand: add s[right] to window state
        window_state[s[right]] = window_state.get(s[right], 0) + 1

        # 2. Shrink: while window is invalid, remove from left
        while not is_valid(window_state):
            window_state[s[left]] -= 1
            if window_state[s[left]] == 0:
                del window_state[s[left]]
            left += 1

        # 3. Update answer
        best = max(best, right - left + 1)

    return best
int slidingWindow(String s) {
    int left = 0, best = 0;
    Map<Character, Integer> window = new HashMap<>();

    for (int right = 0; right < s.length(); right++) {
        // 1. Expand: add s[right]
        window.merge(s.charAt(right), 1, Integer::sum);

        // 2. Shrink: while invalid
        while (!isValid(window)) {
            char c = s.charAt(left);
            window.merge(c, -1, Integer::sum);
            if (window.get(c) == 0) window.remove(c);
            left++;
        }

        // 3. Update answer
        best = Math.max(best, right - left + 1);
    }
    return best;
}
int slidingWindow(string s) {
    int left = 0, best = 0;
    unordered_map<char, int> window;

    for (int right = 0; right < s.size(); right++) {
        // 1. Expand
        window[s[right]]++;

        // 2. Shrink
        while (!isValid(window)) {
            window[s[left]]--;
            if (window[s[left]] == 0) window.erase(s[left]);
            left++;
        }

        // 3. Update
        best = max(best, right - left + 1);
    }
    return best;
}
function slidingWindow(s) {
    let left = 0, best = 0;
    const window = new Map();

    for (let right = 0; right < s.length; right++) {
        // 1. Expand
        window.set(s[right], (window.get(s[right]) || 0) + 1);

        // 2. Shrink
        while (!isValid(window)) {
            window.set(s[left], window.get(s[left]) - 1);
            if (window.get(s[left]) === 0) window.delete(s[left]);
            left++;
        }

        // 3. Update
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Variations

Fixed-Size Window

When the window size K is given, you don’t need the while loop — just slide by adding one element to the right and removing one from the left.

Code

def fixed_window(nums, k):
    """Fixed-size window: max sum of subarray of size k."""
    window_sum = sum(nums[:k])
    best = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # slide
        best = max(best, window_sum)

    return best
int fixedWindow(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];
    int best = windowSum;

    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}
int fixedWindow(vector<int>& nums, int k) {
    int windowSum = accumulate(nums.begin(), nums.begin() + k, 0);
    int best = windowSum;

    for (int i = k; i < nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];
        best = max(best, windowSum);
    }
    return best;
}
function fixedWindow(nums, k) {
    let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
    let best = windowSum;

    for (let i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

Minimum Window (Shrink to Find Shortest)

When finding the shortest valid window, the template flips: expand until valid, then shrink while still valid, recording the minimum length.

Frequency-Constrained Window

When the constraint is “at most K distinct characters” or “at most K replacements allowed,” the isValid check becomes a frequency comparison.

Complexity

Variant Time Space
Fixed window O(n) O(1) or O(k)
Variable window O(n) O(alphabet size)

Why O(n)? Each element is added to the window exactly once (right pointer) and removed at most once (left pointer). Two pointers, each traversing the array once = 2n operations total.

Common Mistakes

Practice Problems

Key Takeaways