Mastering the Sliding Window Pattern

Sliding window is the go-to pattern when you need to operate on a contiguous subarray or substring. Instead of recalculating from scratch every time, you slide a window over the array and update results incrementally.

When to Use It

Use sliding window when the problem asks about:

Maximum/minimum sum of a subarray of size k
Longest/shortest substring with a certain property
Number of subarrays satisfying a condition
Contiguous elements with constraints

Fixed-Size Window Template

typescript
function maxSumSubarray(nums: number[], k: number): number {
  let maxSum = 0
  let windowSum = 0

  for (let i = 0; i < nums.length; i++) {
    windowSum += nums[i] // add new element

    // when window reaches size k
    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum)
      windowSum -= nums[i - k + 1] // remove oldest element
    }
  }

  return maxSum
}

Visualization

For nums = [1, 3, 5, 2, 8, 4], k = 3:

Window 1: [1 3 5] 2 8 4 → sum = 9
Window 2: 1 [3 5 2] 8 4 → sum = 10
Window 3: 1 3 [5 2 8] 4 → sum = 15  ← max
Window 4: 1 3 5 [2 8 4] → sum = 14

Variable-Size Window Template

Used for "longest substring with at most K distinct characters" type problems.

typescript
function longestSubstringKDistinct(s: string, k: number): number {
  const map = new Map<string, number>()
  let left = 0
  let maxLen = 0

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

    // shrink window while invalid
    while (map.size > k) {
      const leftChar = s[left]
      map.set(leftChar, map.get(leftChar)! - 1)
      if (map.get(leftChar) === 0) map.delete(leftChar)
      left++
    }

    // window is valid now
    maxLen = Math.max(maxLen, right - left + 1)
  }

  return maxLen
}

4 Classic Problems

1. Best Time to Buy and Sell Stock

typescript
function maxProfit(prices: number[]): number {
  let minPrice = Infinity
  let maxProfit = 0

  for (const price of prices) {
    minPrice = Math.min(minPrice, price)
    maxProfit = Math.max(maxProfit, price - minPrice)
  }

  return maxProfit
}

This is technically a one-sided window: we keep track of the minimum seen so far.

2. Longest Repeating Character Replacement

typescript
function characterReplacement(s: string, k: number): number {
  const count = new Map<string, number>()
  let maxFreq = 0
  let left = 0
  let maxLen = 0

  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) || 0) + 1)
    maxFreq = Math.max(maxFreq, count.get(s[right])!)

    // window size - maxFreq = replacements needed
    while (right - left + 1 - maxFreq > k) {
      count.set(s[left], count.get(s[left])! - 1)
      left++
    }

    maxLen = Math.max(maxLen, right - left + 1)
  }

  return maxLen
}

3. Minimum Size Subarray Sum

typescript
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0
  let sum = 0
  let minLen = Infinity

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

    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return minLen === Infinity ? 0 : minLen
}

4. Permutation in String

typescript
function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false

  const count1 = Array(26).fill(0)
  const count2 = Array(26).fill(0)

  for (let i = 0; i < s1.length; i++) {
    count1[s1.charCodeAt(i) - 97]++
    count2[s2.charCodeAt(i) - 97]++
  }

  let matches = 0
  for (let i = 0; i < 26; i++) {
    if (count1[i] === count2[i]) matches++
  }

  let left = 0
  for (let right = s1.length; right < s2.length; right++) {
    if (matches === 26) return true

    const rightIndex = s2.charCodeAt(right) - 97
    count2[rightIndex]++
    if (count2[rightIndex] === count1[rightIndex]) matches++
    else if (count2[rightIndex] === count1[rightIndex] + 1) matches--

    const leftIndex = s2.charCodeAt(left) - 97
    count2[leftIndex]--
    if (count2[leftIndex] === count1[leftIndex]) matches++
    else if (count2[leftIndex] === count1[leftIndex] - 1) matches--

    left++
  }

  return matches === 26
}

Fixed vs Variable Window

| Type | Use Case | Loop Structure | |------|----------|----------------| | Fixed | Known window size k | Single loop, remove i-k+1 | | Variable | Constraint-based (e.g., at most K distinct) | Expand with right, shrink with left |

How to Recognize Sliding Window Problems

Ask these questions:

Is it about a contiguous subarray/substring?
Is there a size constraint (fixed or variable)?
Can you update the result in O(1) when the window slides?

If yes to all three, sliding window is likely the answer.

Sliding window turns O(n²) brute-force problems into O(n) elegant solutions. The trick is knowing what to maintain as the window moves.