Sliding window is a disciplined way to solve contiguous range problems in linear time by maintaining state incrementally instead of recomputing from scratch.

If you are still recomputing every subarray sum/frequency independently, you are paying O(n^2) for work that should be O(n).

Mental Model

Define a window [left, right] over contiguous elements.

Each step does one or more of:

Expand right -> include new element
Shrink left -> remove old element(s)
Measure answer on current valid window

The central invariant is:

every element enters window at most once (when right passes it)
every element leaves window at most once (when left passes it)

So total pointer movement is O(n), even if there is a while inside a for.

Two Families You Must Separate

Fixed window (size k)

Window size is constant. Perfect when prompt says:

“subarray of size k”
“average of every k elements”
“maximum sum over length k”

Variable window (size changes)

Window expands and shrinks to satisfy a constraint. Typical prompts:

longest substring with at most k distinct chars
minimum length subarray with sum >= target
count subarrays with at most k odds, etc.

Fixed Window: O(1) Update Formula

Instead of recomputing a k-length window sum in O(k), reuse previous window:

nextWindow = prevWindow + enteringValue - leavingValue

Example: max sum of any subarray of size k

function maxSumK(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) return -Infinity

  let windowSum = 0
  for (let i = 0; i < k; i++) windowSum += nums[i]

  let best = windowSum
  for (let right = k; right < nums.length; right++) {
    windowSum += nums[right] - nums[right - k]
    best = Math.max(best, windowSum)
  }
  return best
}

Common fixed-window variants

max average subarray I
number of substrings of length k satisfying condition
rolling hash / rolling checksum style problems

Variable Window: Valid/Invalid Invariant

For variable windows, define a predicate:

isValid(windowState) == true means current window is acceptable

Then:

expand right by one
while invalid, shrink left
update answer (for longest-valid style) after restored validity

Generic template (at-most constraints)

let left = 0
let answer = 0
const state = new Map<string, number>() // adapt as needed

for (let right = 0; right < arr.length; right++) {
  // add arr[right] to state

  while (/* window invalid */) {
    // remove arr[left] from state
    left++
  }

  // window valid here
  answer = Math.max(answer, right - left + 1)
}

This pattern powers a huge fraction of medium interview string/array questions.

Example 1: Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>()
  let left = 0
  let best = 0

  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    if (lastSeen.has(ch) && lastSeen.get(ch)! >= left) {
      left = lastSeen.get(ch)! + 1
    }
    lastSeen.set(ch, right)
    best = Math.max(best, right - left + 1)
  }
  return best
}

Why this jump-left version is strong

Instead of shrinking one step at a time, we jump left directly after duplicate’s previous index. Still O(n), cleaner constant factors.

Example 2: Minimum Size Subarray Sum (Positive Numbers)

function minSubarrayLen(target: number, nums: number[]): number {
  let left = 0
  let sum = 0
  let best = Infinity

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

    while (sum >= target) {
      best = Math.min(best, right - left + 1)
      sum -= nums[left]
      left++
    }
  }
  return best === Infinity ? 0 : best
}

Critical caveat

This works because numbers are non-negative.
If negatives exist, shrinking can increase sum unpredictably and this invariant breaks. Use prefix sum + deque / binary search variants instead depending on problem.

Exact, At-Most, At-Least Windows

Most variable-window problems are one of these forms:

A) Longest with at most K violations

keep window valid with while invalid -> shrink
update max length

B) Minimum with at least target

expand until valid
then shrink aggressively while still valid
update min length during shrink

C) Count of exactly K

Compute:

countExactly(K) = countAtMost(K) - countAtMost(K - 1)

This transform is interview gold for counting subarrays/substrings.

Example 3: Count Subarrays with Exactly K Odd Numbers

function atMostKOdds(nums: number[], k: number): number {
  let left = 0
  let odd = 0
  let count = 0

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] % 2 !== 0) odd++

    while (odd > k) {
      if (nums[left] % 2 !== 0) odd--
      left++
    }

    count += right - left + 1 // all windows ending at right
  }
  return count
}

function numberOfSubarraysExactlyKOdds(nums: number[], k: number): number {
  return atMostKOdds(nums, k) - atMostKOdds(nums, k - 1)
}

Sliding Window Maximum (Monotonic Deque Bridge)

Classic hard problem where plain sum/frequency window state is not enough.

Need max of each size-k window in O(n), not O(nk).

Store candidate indices in decreasing-value order:

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = []
  const deque: number[] = [] // stores indices, values decreasing
  let head = 0 // logical front pointer (avoids O(n) shift)

  for (let i = 0; i < nums.length; i++) {
    // remove out-of-window indices
    if (head < deque.length && deque[head] <= i - k) head++

    // maintain decreasing deque
    while (head < deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop()
    }

    deque.push(i)
    if (i >= k - 1) result.push(nums[deque[head]])

    // occasional compaction so deque doesn't grow unbounded from stale prefix
    if (head > 1024 && head * 2 > deque.length) {
      deque.splice(0, head)
      head = 0
    }
  }

  return result
}

Production note: this head-pointer pattern preserves O(n) behavior in JavaScript as well.

Decision Framework: Sliding Window vs Something Else

Use sliding window when all are true:

data is linear (array/string)
target segment is contiguous
window validity/score can be incrementally updated

Do not force sliding window when:

subsequence (non-contiguous) problems -> DP/greedy
arbitrary range queries repeated many times -> prefix sums/segment trees
constraints are non-monotonic under shrink/expand

Common Bugs Checklist

Updating answer before restoring validity
Using if instead of while for shrink phase
Forgetting to decrement state when moving left
Wrong window length formula (right - left + 1)
Mishandling empty input / k > n / k == 0
Assuming positive numbers where negatives are allowed
Frequency map cleanup mistakes (count drops to 0 but key not removed when needed)

Interview Communication Template

Speak like this:

“I maintain a window [left, right] and a state object.”
“After adding right, I shrink until invariant X is restored.”
“Each index is added and removed at most once, so O(n).”

This communicates correctness, not just coding speed.

Complexity Summary

Variant	Time	Space	Notes
Fixed size	O(n)	O(1)	O(1) update per slide
Variable with map/set	O(n)	O(k) to O(sigma)	depends on tracked state
Monotonic deque window max	O(n)	O(k)	each index pushed/popped once

Why still O(n) with nested loops:

outer right increments n times
inner shrink/deque pops cumulatively at most n times

Total O(2n) style accounting.

Problem Ladder (Recommended)

Easy

Maximum Sum Subarray of Size K
Longest Substring Without Repeating Characters

Medium

Longest Repeating Character Replacement
Permutation in String
Minimum Size Subarray Sum
Fruit Into Baskets (at most 2 distinct)

Hard / high-signal

Minimum Window Substring
Sliding Window Maximum
Subarrays with K Different Integers (exactly K via at-most trick)

Final Takeaway

Sliding window is an invariant-maintenance technique, not a memorized snippet.

Define:

what state your window tracks
what “valid” means
when to update answer
why pointer movement is monotonic

Do this consistently and most contiguous optimization/counting problems become predictable and linear.