Sliding Window: Fixed and Variable Width Patterns

Terminology

Term	Definition
Sliding window	A technique that maintains a contiguous subarray (or substring) bounded by two pointers, sliding across the input to avoid redundant recomputation.
Fixed-width window	A window of constant size $k$ that advances one element at a time. Both pointers move together.
Variable-width window	A window whose size changes dynamically. The right pointer expands to include elements, the left pointer shrinks to restore a constraint.
Expand/shrink	The two phases of a variable window: expand adds the next element, shrink removes elements from the left until the window satisfies the required condition.

Subarray A contiguous slice of an array, defined by a start and end index. Every window corresponds to a subarray. Amortized $O(n)$ Although the inner (shrink) loop may run multiple times per expansion step, each element enters and leaves the window at most once, so total work across all iterations is $O(n)$. Hash map (frequency map) A data structure mapping elements to their counts inside the current window. Used to track character frequencies or element occurrences in $O(1)$ per operation. Invariant A condition that must hold true throughout the algorithm. For sliding window, the invariant describes what makes the current window "valid."

What & Why

Many array and string problems ask you to find an optimal contiguous subarray or substring: the maximum sum of k consecutive elements, the longest substring with at most 2 distinct characters, or the smallest subarray whose sum exceeds a target.

The brute-force approach checks every possible subarray, which is O(n^2) or worse. The sliding window technique reduces this to O(n) by maintaining a window that slides across the input. Instead of recomputing from scratch for each position, you incrementally update the window state as you add one element on the right and (possibly) remove elements from the left.

There are two flavors:

• Fixed-width: the window size is given (e.g., "max average of k elements"). Both pointers advance in lockstep.
• Variable-width: the window grows and shrinks to satisfy a constraint (e.g., "smallest subarray with sum \geq target"). The right pointer expands, the left pointer contracts.

The pattern appears in dozens of LeetCode problems and is one of the highest-value techniques for coding interviews.

How It Works

Fixed-Width Window

With a fixed window of size k, compute the initial window sum, then slide by adding the incoming element and subtracting the outgoing element.

Variable-Width Window (Expand/Shrink)

For problems like "longest substring without repeating characters," the window expands by moving the right pointer and shrinks by moving the left pointer whenever the window violates the constraint.

The key insight: each element enters the window exactly once (when the right pointer passes it) and leaves at most once (when the left pointer passes it). This gives an amortized O(n) total, even though there is an inner shrink loop.

Complexity Analysis

Problem	Brute Force	Sliding Window	Space
Max sum of $k$ elements	$O(nk)$	$O(n)$	$O(1)$
Longest substring, no repeats	$O(n^2)$	$O(n)$	$O(\min(n, |\Sigma|))$
Smallest subarray with sum $\geq$ target	$O(n^2)$	$O(n)$	$O(1)$
Max of all $k$-size windows	$O(nk)$	$O(n)$ with deque	$O(k)$

Why O(n)?

Each pointer moves from index 0 to at most index $n - 1$. The left pointer never moves backward. Total pointer movements:

For the fixed-width variant, the window slides exactly $n - k + 1$ times, each step doing $O(1)$ work:

Implementation

Fixed-Width: Maximum Sum of k Consecutive Elements

ALGORITHM MaxSumFixedWindow(A, n, k)
  INPUT: array A of size n, window size k
  OUTPUT: maximum sum of any k consecutive elements

  windowSum = 0
  FOR i = 0 TO k - 1 DO
    windowSum = windowSum + A[i]
  END FOR

  best = windowSum

  FOR i = k TO n - 1 DO
    windowSum = windowSum + A[i] - A[i - k]
    best = MAX(best, windowSum)
  END FOR

  RETURN best
END

Variable-Width: Longest Substring Without Repeating Characters

ALGORITHM LongestUniqueSubstring(s, n)
  INPUT: string s of length n
  OUTPUT: length of longest substring with all unique characters

  freq = empty hash map
  left = 0
  best = 0

  FOR right = 0 TO n - 1 DO
    freq[s[right]] = freq[s[right]] + 1

    WHILE freq[s[right]] > 1 DO
      freq[s[left]] = freq[s[left]] - 1
      left = left + 1
    END WHILE

    best = MAX(best, right - left + 1)
  END FOR

  RETURN best
END

Variable-Width: Smallest Subarray with Sum >= Target

ALGORITHM MinSubarraySum(A, n, target)
  INPUT: array A of size n (positive integers), target sum
  OUTPUT: length of smallest subarray with sum >= target, or 0 if none

  left = 0
  windowSum = 0
  best = INFINITY

  FOR right = 0 TO n - 1 DO
    windowSum = windowSum + A[right]

    WHILE windowSum >= target DO
      best = MIN(best, right - left + 1)
      windowSum = windowSum - A[left]
      left = left + 1
    END WHILE
  END FOR

  IF best = INFINITY THEN RETURN 0
  RETURN best
END

Real-World Applications

• Network throughput monitoring: compute rolling averages over fixed time windows to detect bandwidth spikes or drops.
• Rate limiting: sliding window counters track request counts within a moving time frame, used in API gateways and load balancers.
• Streaming analytics: real-time dashboards compute aggregates (sum, average, max) over the most recent $k$ data points using fixed-width windows.
• DNA sequence analysis: find the longest substring matching a pattern constraint (e.g., at most 2 distinct nucleotides) in genomic data.
• Text editors: search-and-highlight features scan documents with a variable window to find matching substrings efficiently.

Key Takeaways

• Sliding window converts $O(n^2)$ brute-force subarray scans into $O(n)$ single-pass algorithms by reusing computation from the previous window position
• Fixed-width windows slide both pointers in lockstep, updating the aggregate with one addition and one subtraction per step
• Variable-width windows use an expand/shrink loop: the right pointer grows the window, the left pointer restores the invariant
• The amortized $O(n)$ guarantee comes from the fact that each element enters and exits the window at most once across the entire run
• When you see "contiguous subarray/substring" plus "optimal length/sum," think sliding window first