Overview#

Sliding Window is a common form of the two-pointer technique applied to contiguous interval problems. It maintains a window [left, right] or [left, right), and as the right pointer expands and the left pointer contracts, it handles subarray or substring problems in O(n) time.

Prerequisites

• Two Pointers: the window’s left and right boundaries are maintained by two pointers
• Hash Map / Counter: tracks the state of characters or elements within the window
• Interval Invariant: clearly defines what condition the window currently satisfies or fails to satisfy

Problem Definition#

Given an array or string, find a contiguous interval that satisfies some condition, such as maximum length, minimum length, fixed-length optimum, or coverage relationship.

Core Principle: Step-by-Step Illustration#

Taking the variable-length window as an example, the right pointer is responsible for expansion, and the left pointer is responsible for restoring the condition:

1
s:      a  b  c  a  b  c  b  b
2
index:  0  1  2  3  4  5  6  7
3
window: [left ...... right]

The reason sliding window is O(n) is that each element is added by the right pointer at most once and removed by the left pointer at most once.

Detailed Algorithm Steps#

1
Algorithm: VariableSlidingWindow(nums)
2
Input: array or string nums
3
Output: the optimal window that satisfies the condition
4

5
1. left ← 0
6
2. Initialize the window state window
7
3. for right from 0 to nums.length - 1:
8
4.     Add nums[right] to window
9
5.     while window does not satisfy the constraint:
10
6.         Remove nums[left] from window
11
7.         left ← left + 1
12
8.     Update the answer with the current window
13
9. Return the answer

Complexity Analysis:

TypeScript Implementation#

1
function maxSumSubarray(nums: number[], k: number): number {
2
  let sum = 0;
3

4
  for (let i = 0; i < k; i++) {
5
    sum += nums[i];
6
  }
7

8
  let best = sum;
9
  for (let right = k; right < nums.length; right++) {
10
    sum += nums[right] - nums[right - k];
11
    best = Math.max(best, sum);
12
  }
13

14
  return best;
15
}

1
function findMaxAverage(nums: number[], k: number): number {
2
  return maxSumSubarray(nums, k) / k;
3
}

1
function lengthOfLongestSubstring(s: string): number {
2
  const window = new Map<string, number>();
3
  let left = 0;
4
  let best = 0;
5

6
  for (let right = 0; right < s.length; right++) {
7
    const char = s[right];
8
    window.set(char, (window.get(char) ?? 0) + 1);
9

10
    while (window.get(char)! > 1) {
11
      const removed = s[left];
12
      window.set(removed, window.get(removed)! - 1);
13
      left++;
14
    }
15

16
    best = Math.max(best, right - left + 1);
17
  }
18

19
  return best;
20
}

1
function minSubArrayLen(target: number, nums: number[]): number {
2
  let left = 0;
3
  let sum = 0;
4
  let best = Infinity;
5

6
  for (let right = 0; right < nums.length; right++) {
7
    sum += nums[right];
8

9
    while (sum >= target) {
10
      best = Math.min(best, right - left + 1);
11
      sum -= nums[left];
12
      left++;
13
    }
14
  }
15

16
  return best === Infinity ? 0 : best;
17
}

1
function minWindow(s: string, t: string): string {
2
  const need = new Map<string, number>();
3
  const window = new Map<string, number>();
4

5
  for (const char of t) {
6
    need.set(char, (need.get(char) ?? 0) + 1);
7
  }
8

9
  let left = 0;
10
  let valid = 0;
11
  let start = 0;
12
  let minLength = Infinity;
13

14
  for (let right = 0; right < s.length; right++) {
15
    const char = s[right];
16
    if (need.has(char)) {
17
      window.set(char, (window.get(char) ?? 0) + 1);
18
      if (window.get(char) === need.get(char)) valid++;
19
    }
20

21
    while (valid === need.size) {
22
      if (right - left + 1 < minLength) {
23
        start = left;
24
        minLength = right - left + 1;
25
      }
26

27
      const removed = s[left];
28
      left++;
29

30
      if (need.has(removed)) {
31
        if (window.get(removed) === need.get(removed)) valid--;
32
        window.set(removed, window.get(removed)! - 1);
33
      }
34
    }
35
  }
36

37
  return minLength === Infinity ? '' : s.slice(start, start + minLength);
38
}

Engineering Optimization: Window State Must Be Incrementally Maintainable#

The premise of sliding window is that when the window changes, the state can be updated quickly.

If the window state cannot be updated in O(1) or amortized O(1), the sliding window may degrade, and you should consider a monotonic queue, heap, or other structures.

Applications and Limitations#

Summary#

Key Points:

1. Sliding window is suitable for contiguous subarray and substring problems.
2. Fixed-length windows focus on balancing entry and exit; variable-length windows focus on maintaining validity.
3. Each element enters and leaves the window at most once, so it is typically O(n).
4. Define the window state and shrink condition before writing code.

Related Articles#

• Sliding Window Core Code Template: Three Questions to Solve All Substring and Subarray Problems — Condenses the categories in this article into a reusable skeleton: when to expand, when to shrink, when to update the result, and why the window interval is written as left-closed right-open
• Array Two Pointers: An Optimization Tool from O(n²) to O(n) — The two-pointer idea behind sliding window
• Classic Array Two-Pointer Exercises (Part 1): One-Dimensional Arrays and Strings — Fast-slow pointers, left-right pointers, and Dutch national flag
• Hash Map: From Two Sum to Subarray Sum — Sliding window is often used in conjunction with hash counting