DEV Community

The Architect
The Architect

Posted on

Algorithmic Patterns: The Ultimate Guide to Sliding Window

#algorithms #dsa #leetcode #programming

The Sliding Window pattern is one of the most vital algorithmic techniques for optimizing array and string problems. Instead of repeatedly processing overlapping subarrays - which leads to brute-force quadratic O(N^2) or O(N*K) complexities, the sliding window technique reuses previous computations to achieve linear time complexity $O(N)$.

In this guide, we will break down the mechanics, core variations, identification rules, real-world applications, and a curated list of 18 LeetCode problems with key solution strategies.

💡 What is the Sliding Window Pattern?

A sliding window performs operations over a contiguous sub-segment (subarray or substring) of data structure. As the window "slides" across the array from left to right, elements entering and leaving the window are updated incrementally.

Time Complexity Comparison

  • Brute-Force Nested Loops: O(N^2) or O(N * K)
  • Sliding Window Strategy: O(N) (each element is processed at most twice: once entering and once leaving)

🛠️ Recognition & Identification Rules

When to Use Sliding Window

  1. Contiguous Input: The problem requires evaluating contiguous subarrays or substrings.
  2. Window Metric Criteria: You need to calculate statistics such as minimum/maximum length, sum, average, or character frequency targets.
  3. Monotonicity Property: Expanding the window strictly increases (or maintains) a target metric, while shrinking the window strictly decreases it (e.g., sum > K or at most K distinct elements over positive numbers).

When NOT to Use Sliding Window

  • Negative Numbers in Sum Constraints: If an array contains negative numbers and you are tracking a cumulative sum, expanding the window does not monotonically increase the sum. Use Prefix Sum + HashMap instead.
  • Non-Contiguous Sequences: If the problem asks for subsequences (where elements do not need to be adjacent), sliding window fails.
  • Non-Monotonic Metrics: If moving pointers does not give a predictable increase or decrease in your decision metric.

🔄 Fixed vs. Variable Length Sliding Window

Sliding window algorithms fall into two primary structural variants:

Feature Fixed-Length Window Variable-Length Window
Window Boundary Fixed size $K$ Expands and contracts dynamically based on conditions
Pointer Movement left and right advance together right expands continuously; left contracts when condition breaks
Core Goal Calculate a target metric (sum, max, avg, frequency match) across all subarrays of exact length $K$ Find the longest, shortest, or total count of valid subarrays matching a criterion
State Operations Add element at right, drop element at left Add element at right; loop-shrink from left while invalid (or valid)

📊 Visualizing Window Mechanics

1. Fixed-Length Sliding Window

In a fixed window, both pointers maintain a constant distance $K$.

flowchart LR
    subgraph Iteration 1
        A1["[ A  B  C ] D  E"]
    end
    subgraph Iteration 2
        A2["A [ B  C  D ] E"]
    end
    subgraph Iteration 3
        A3["A  B [ C  D  E ]"]
    end

    Iteration 1 -->|Slide Right: Add D, Remove A| Iteration 2
    Iteration 2 -->|Slide Right: Add E, Remove B| Iteration 3
Enter fullscreen mode Exit fullscreen mode

2. Variable-Length Sliding Window

In a variable window, right expands the window until a condition is broken, prompting left to shrink the window back into a valid state.

flowchart TD
    Start([Start Array Traversal]) --> Expand[Add arr[right] to Window]
    Expand --> Check{Is Window Valid?}
    Check -- Yes --> UpdateAns[Update Best Result Max/Min Length]
    UpdateAns --> IncrementRight[right++]
    Check -- No --> Shrink[Remove arr[left] from Window]
    Shrink --> IncrementLeft[left++]
    IncrementLeft --> Check
    IncrementRight --> LoopEnd{End of Array?}
    LoopEnd -- No --> Expand
    LoopEnd -- Yes --> End([Return Result])
Enter fullscreen mode Exit fullscreen mode

🌐 Real-World Applications

  1. Financial Systems: Calculating moving averages of real-time stock prices over $N$-day windows.
  2. Network Engineering: API Rate Limiting (e.g., Sliding Window Log/Counter algorithms to restrict requests per second).
  3. Audio/Video Processing: Processing live audio streaming chunks of continuous audio buffers.

💻 Code Blueprints

Fixed-Length Template (Java/Python Concept) 

def fixed_sliding_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]  # Add incoming, subtract outgoing
        max_sum = max(max_sum, window_sum)

    return max_sum
Enter fullscreen mode Exit fullscreen mode

Variable-Length Template 

def variable_sliding_window(arr, condition_target):
    left = 0
    window_state = 0
    best_res = 0

    for right in range(len(arr)):
        # 1. Include right element
        window_state += arr[right]

        # 2. Shrink window while invalid
        while not is_valid(window_state, condition_target):
            window_state -= arr[left]
            left += 1

        # 3. Update result
        best_res = max(best_res, right - left + 1)

    return best_res
Enter fullscreen mode Exit fullscreen mode

🏋️ Problem Playbook & Key Strategies

Category A: Fixed-Length Window Problems

1. Maximum Average Subarray I (LeetCode 643)

  • Strategy: Maintain a window sum of length k. Slide across the array by adding nums[right] and subtracting nums[right - k]. Finally, return max_sum / k.

2. Minimum Recolors to Get K Consecutive Black Blocks (LeetCode 2379)

  • Strategy: Use a fixed window of size k. Count the number of white blocks ('W') inside the current window. Track the minimum white block count across all windows.

3. Subarrays Size K with Average Greater than or Equal to Threshold (LeetCode 1343)

  • Strategy: Transform the target average to target sum: target_sum = (threshold * k). Maintain a running sum of window size k and increment the count whenever window_sum >= target_sum.

4. Grumpy Bookstore Owner (LeetCode 1052)

  • Strategy: Calculate baseline satisfied customers without using technique. Then, run a fixed window of length minutes to maximize the extra unsatisfied customers converted to satisfied. Add maximum extra gain to baseline.

5. Contains Duplicate II (LeetCode 219)

  • Strategy: Use a dynamic HashSet acting as a sliding window of max size $k$. For each element, check if it exists in the set. If yes, return true. If window size exceeds $k$, remove nums[i - k] from the set.

6. Defuse the Bomb (LeetCode 1658)

  • Strategy: Circular array windowing. Determine window bounds depending on whether k > 0 or k < 0. Slide a fixed window of length |k| across the array using modulo index mapping: index % N.

Category B: Dynamic Variable-Length Window Problems

7. Longest Substring Without Repeating Characters (LeetCode 3)

  • Strategy: Maintain a lastIndexSeen HashMap. When a duplicate character is encountered at right, jump left = max(left, lastIndexSeen[char] + 1) to keep the window unique.

8. Max Consecutive Ones III (LeetCode 1004)

  • Strategy: Maintain a zero counter within the window. Whenever zero count exceeds k, shrink from left until zero count is less than k. Record max window length (right - left + 1).

9. Fruit Into Baskets (LeetCode 904)

  • Strategy: Equivalent to "Longest Subarray with at most 2 Distinct Elements". Use a frequency map. Shrink from left when map.size() > 2.

10. Minimum Size Subarray Sum (LeetCode 209)

  • Strategy: Expand right to increase running sum. Once sum >= target, contract left in a inner while loop to find the minimum dynamic window length while updating answer.

11. Subarray Product Less Than K (LeetCode 713)

  • Strategy: Expand right and multiply into current_product. If current_product >= k, divide out nums[left]. The number of valid subarrays ending at right is (right - left + 1).

12. Longest Repeating Character Replacement (LeetCode 424)

  • Strategy: Track the maximum frequency of any single character in the current window (maxFreq). The window is valid if (windowLength - maxFreq) <= K. Otherwise, shrink from left.

Category C: Substring Matching & Advanced Patterns

13. Permutation in String (LeetCode 567)

  • Strategy: Fixed window equal to s1.length(). Maintain two 26-element frequency arrays (or one diff array). Slide across s2 and check if frequency counts match.

14. Find All Anagrams in a String (LeetCode 438)

  • Strategy: Same mechanics as LC 567. Whenever character frequency match is found, append starting index left to answer list.

15. Maximum Points You Can Obtain from Cards (LeetCode 1423)

  • Strategy: Inverted Sliding Window. Picking k cards from beginning or end is equivalent to finding a continuous subarray of size (N - K) with the minimum total sum. Result = Total Sum - (Min Subarray Sum).

16. Minimum Window Substring (LeetCode 76)

  • Strategy: Dynamic dynamic window using target map & match counter. Expand right until all target characters are satisfied. Then shrink left to minimize length while retaining validity.

17. Sliding Window Maximum (LeetCode 239)

  • Strategy: Multi-pattern (Sliding Window + Monotonic Deque). Maintain indices in a Monotonic Deque in strictly decreasing order of value. The front of deque always holds the max element index for the current window in O(1) lookup time.

18. Substring with Concatenation of All Words (LeetCode 30)

  • Strategy: Run multiple parallel sliding windows offset by word length (len(word)). Track word occurrences using a frequency map for O(N) overall time.

🎯 Summary Checklist

Before choosing Sliding Window, ask yourself:

  1. Is the problem dealing with a contiguous sequence?
  2. Does expanding/shrinking the window have a monotonic impact on the validity condition?
  3. Are all array elements non-negative when target sums are involved?

Mastering this single pattern unlocks quick solutions to dozens of popular interview problems. Happy coding!

💡 Get the Full 10-Page System Design Guide

Subscribe to The Tech Builder Newsletter to instantly get the full, unredacted guide for free.

Every week, subscribers receive:

  • 🎯 Deep-dive production postmortems & system design trade-off analysis.
  • 🛠️ Real-world architecture playbooks for Senior ICs, Tech Leads, and Architects.
  • 🎁 Instant Bonus: Get the Full 6-Month Prep Tracker & Study Schedule + 10-Page System Design Cheat Sheet immediately upon subscribing.

👉 Get the Full System Design Cheat Sheet

Top comments (0)