How to Use the Sliding Window Technique for Array Problems

The sliding window technique is a two-pointer strategy that processes contiguous segments of an array in O(n) time by maintaining a dynamic subarray "window" that expands and contracts based on specific constraints.

The azl397985856/leetcode repository provides comprehensive implementations of the sliding window technique for array problems, demonstrating how this pattern solves subarray and substring challenges without nested loops. By ensuring each element is added to the window exactly once and removed at most once, the approach guarantees linear time complexity for problems that would otherwise require quadratic brute-force solutions.

Two Fundamental Sliding Window Variants

All sliding window implementations in the repository follow one of two pointer-movement strategies depending on whether the window size is predetermined or dynamic.

Fixed-Size Windows

Use fixed-size windows when you must evaluate every contiguous subarray of length k, such as finding the maximum sum of any k consecutive elements. Both pointers (left and right) initialize at the start, with right advancing by one each iteration while left = right - k + 1 maintains constant window width.

Variable-Size Windows

Use variable-size windows when searching for the smallest or largest subarray satisfying a condition, such as a sum greater than or equal to a target value. Both pointers start at index 0. The right pointer expands the window until the condition is met, then the left pointer shrinks the window from the left as much as possible while preserving validity.

The Generic Sliding Window Template

According to the thinkings/slide-window.md file in the repository, the canonical implementation follows these steps:

1. Initialize left = 0 and an answer variable to store results.
2. Iterate right from 0 to end of the array.
3. Update window state (sum, frequency map, etc.) by adding the element at right.
4. While the window does not satisfy the problem constraints, advance left and adjust the window state by removing the element at left.
5. Update the answer with the current window's value if applicable.
6. Continue until right reaches the array end.

This template guarantees O(n) complexity because each element enters the window exactly once (when right passes it) and exits at most once (when left passes it).

Variable-Size Window Implementation Examples

The following examples from the repository demonstrate how to apply the template to classic LeetCode problems.

Minimum Size Subarray Sum (LeetCode 209)

Located at problems/209.minimum-size-subarray-sum.md, this solution finds the smallest length of a contiguous subarray whose sum is at least target.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = total = 0
        best = len(nums) + 1               # sentinel larger than any possible answer

        for right in range(len(nums)):
            total += nums[right]            # expand window

            while total >= target:          # shrink while condition holds

                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if best == len(nums) + 1 else best

The algorithm expands the window by advancing right and accumulates total. Once total >= target, it enters a shrinking phase where left moves rightward, subtracting elements from total until the condition fails, ensuring the minimum valid window is found.

Longest Substring Without Repeating Characters (LeetCode 3)

This implementation from problems/3.longest-substring-without-repeating-characters.md uses a hash map to track character indices, illustrating how to handle window state with non-numeric data.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = ans = 0
        seen = {}
        for right, ch in enumerate(s):
            if ch in seen and seen[ch] >= left:
                left = seen[ch] + 1        # move left past previous occurrence

            seen[ch] = right
            ans = max(ans, right - left + 1)
        return ans

Here, the window state consists of character positions in the seen dictionary. When a duplicate is detected within the current window (seen[ch] >= left), left jumps past the previous occurrence, effectively shrinking the window to maintain uniqueness.

Essential Repository Files for Sliding Window Study

The azl397985856/leetcode repository contains several reference documents for mastering this technique:

• thinkings/slide-window.md: Core conceptual guide with diagrams and pseudocode explaining the pointer movement mechanics.
• thinkings/slide-window.en.md: English translation of the main sliding window tutorial for international readers.
• problems/209.minimum-size-subarray-sum.md: Concrete implementation of a minimum-window problem with positive integer arrays.
• problems/3.longest-substring-without-repeating-characters.md: Example of maximum-window logic using hash maps for character frequency tracking.
• thinkings/string-problems.md: Extended discussion on string-oriented sliding window applications including anagram detection and permutation checks.

Summary

• The sliding window technique solves array and string problems involving contiguous subarrays in linear O(n) time.
• Fixed-size windows maintain constant width k by moving both pointers in lockstep, ideal for problems like "maximum sum of k consecutive elements."
• Variable-size windows expand with the right pointer and contract with the left pointer to find optimal bounds for conditions like "smallest sum ≥ target."
• Each element is processed at most twice (once added, once removed), ensuring optimal performance.
• The repository provides ready-to-use templates in thinkings/slide-window.md and working solutions in the problems/ directory.

Frequently Asked Questions

What is the time complexity of the sliding window technique?

The sliding window technique operates in O(n) time complexity where n is the array length, because each pointer traverses the array at most once. The right pointer advances monotonically to the end, while the left pointer only moves forward during shrinking phases, ensuring no element is processed more than twice.

Can sliding window be used with negative numbers in the array?

Standard sliding window techniques that rely on monotonically increasing or decreasing window properties (like sum-based conditions) typically require non-negative numbers to guarantee correctness. When negative numbers are present, shrinking the window does not guarantee the sum will decrease, potentially requiring alternative approaches like prefix sums with hash maps instead of the classic two-pointer sliding window.

How do I decide between fixed-size and variable-size sliding windows?

Use fixed-size when the problem explicitly asks for subarrays of a specific length k or when every window of size k must be evaluated. Use variable-size when searching for the minimum or maximum length subarray satisfying a specific condition (sum, unique characters, etc.), where the optimal window size is unknown beforehand.

Are there sliding window implementations for languages other than Python in the repository?

The azl397985856/leetcode repository primarily demonstrates solutions in JavaScript and Python, with the thinkings/slide-window.md file providing language-agnostic pseudocode that can be adapted to any supported language. The core logic remains identical across implementations, requiring only syntactical adjustments for pointer manipulation and data structures.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}