Sliding Window

Mindmap

Sliding Window

Types

By window size

Fixed window

Variable window

By goal

Find in window

Longest / Max

Shortest / Min

Others

Count subarrays

Less than K

AtMost(K-1)

Exactly K

AtMost(K) - AtMost(K-1)

Return Indices

Data Structures

Frequency

dict

Unique elements

dict

set

Sum / Avg / Product

Prefix sum

Maintain total

Min / Max element

Deque

O(1)

SortedList

O(log n)

Monoqueue

Requirement

Subarray / Substring

contiguous elements

Only positives

sliding window works

With negatives

use prefix sum instead

Input Structure

Array

manipulate subarray

String

manipulate substring

Phases

every problem

Expansion

Rapid

while loop

Single element

Shrinking

Rapid

while loop

Single element

Problem Logic

apply when window is valid

+

−

⟲

⛶

Problem Categories

Sliding Window

Fixed Window

Naïve Sum / Avg

Hashmap

Duplicate

Unique

Anagrams

Count

Math

Swaps

Misc

Heap

Sorting

Bit Manip.

Longest Sub

Consecutive X

1 Pass

>1 Pass

Hashmap

Unique

K Distinct

Misc

Depends on prev

Shortest Sub

Naive

Two Strings

Return Count / Idx

Naïve Sum / Avg

Longest Sub

Depends on prev

At Most K

Less than K

Exactly K

+

−

⟲

⛶

Anatomy: Expansion, Shrinking, Logic

Every sliding window has the same three phases - Expansion, Shrinking, Logic. What changes between Fixed / Longest / Shortest is which phase uses a while loop (rapid) and which uses a one-line shift (single element), and where the Logic sits.

Pattern	Expansion	Shrinking	Logic placement
Fixed (size = k)	while until size hits k	one-line (remove 1, left += 1)	between expansion and shrinking - window is always size k here
Longest - Sliding	one-line (right += 1)	while invalid (rapid shrink to valid)	after shrink, unconditional maxi = max(maxi, right - left)
Longest - Shifting	one-line (right += 1)	one-line if invalid (window slides, never shrinks below peak)	after the if, unconditional maxi = max(maxi, right - left)
Shortest	while until valid (rapid grow)	while still valid (rapid shrink)	inside the shrink loop - every valid window updates mini before removing

Fixed window

Window has a constant size k. Grow to k, do work, slide by one forever.

while right < n:

# Expansion - rapid (while)

while right < n and right - left < k:

total += arr[right]

right += 1

# Logic - window is exactly size k here

ans = max(ans, total)

# Shrinking - one-line shift

total -= arr[left]

left += 1

Longest window - Sliding (full shrink-to-valid)

Window can shrink by many elements when it becomes invalid. Use when the constraint requires exact equality or duplicate purging (e.g. dup removal, exact-sum, vowel-order).

while right < n:

# Expansion - one-line

counter[s[right]] += 1

right += 1

# Shrinking - rapid (while), restore validity

while left < right and invalid:

counter[s[left]] -= 1

left += 1

# Logic - unconditional, every iteration

maxi = max(maxi, right - left)

Longest window - Shifting (preferred for max-length-with-inequality)

Window never actually shrinks below its peak - it just slides forward by one when invalid. Works whenever the constraint is ≤ something (k distinct, k flips, k cost). See Shifting Window variant in most longest problems.

while right < n:

# Expansion - one-line

counter[s[right]] += 1

right += 1

# SHIFTing instead of Shrinking! - one-line if

if invalid:

counter[s[left]] -= 1

left += 1

# Logic - unconditional

maxi = max(maxi, right - left)

Shortest window

Window grows until just barely valid, then shrinks as long as it stays valid - recording the smallest valid size along the way. Both phases are rapid while loops; the Logic lives inside the shrink loop because every step inside it is a valid candidate.

while right < n:

# Expansion - rapid (while), grow until valid

while right < n and total < target:

total += nums[right]

right += 1

# Shrinking - rapid (while), shrink while still valid

while left < right and total >= target:

# Logic - every valid window is a candidate

mini = min(mini, right - left)

total -= nums[left]

left += 1

return mini if mini != float("inf") else 0

Quick mental model

• while = rapid phase (the phase doing the heavy lifting for the goal)
• One-line = passive phase (just slides past)
• Logic sits next to the rapid phase that produces valid windows:
  • Fixed: after Expansion (Expansion produces the valid size-k window)
  • Longest: after Shrinking (Shrinking restores validity)
  • Shortest: inside Shrinking (each step inside is its own valid candidate)