Skip to content

Volume ITechnology

4.6.0 — Sliding Window: The Pattern ​

Recognition cue. The problem asks for the longest, shortest, or best contiguous stretch, meaning a substring or a subarray, that satisfies some condition. The word contiguous is the clue. If the problem allows gaps, it is a subsequence, and that is dynamic programming, not a window.

The move. Two indices that both only ever move forwards. O(n^2) becomes O(n).

The two shapes ​

Almost every window problem is one of these two, and knowing which one you are in before writing anything saves most of the confusion.

python
# A. LONGEST valid window — shrink WHILE INVALID, record AFTER
left = 0  # (1)
for right in range(len(a)):
    add(a[right])  # (2)
    while not valid():  # (3)
        remove(a[left])  # (4)
        left += 1
    best = max(best, right - left + 1)  # (5)

# B. SHORTEST valid window — shrink WHILE VALID, record INSIDE
left = 0  # (6)
for right in range(len(a)):
    add(a[right])  # (7)
    while valid():  # (8)
        best = min(best, right - left + 1)  # (9)
        remove(a[left])  # (10)
        left += 1

A third shape is the fixed-size window, where the length is given. There is no while at all — you add the character entering on the right and remove the one leaving on the left, in one step.

python
# C. FIXED size k
for right in range(len(a)):
    add(a[right])  # (11)
    if right >= k:  # (12)
        remove(a[right - k])
    if right >= k - 1:  # (13)
        record()

The templates, line by line.

(1) Template A finds the longest window that obeys a rule. Its left edge starts at 0. (2) Grow the window by one item on the right, every time. (3) While the window breaks the rule, (4) drop items from the left. (5) Now the window is allowed, so record its length if it is the longest so far.

(6) Template B finds the shortest window that obeys a rule. (7) Grow on the right. (8) While the window is still allowed, (9) record it first, because it may be the shortest yet, (10) then shrink from the left to try for something shorter. The only differences from A are "while valid" instead of "while not valid", and recording inside the loop instead of after it.

(11) Template C keeps a window of exactly k items. Add the new item on the right. (12) Once more than k items have been added, remove the one that just fell off the left, at position right - k. (13) From the moment the first full window exists, record each one.

Why it is linear ​

Both pointers only move forwards, and left never passes right. So across the whole run, left advances at most n times in total — not n times per iteration of the outer loop. A while inside a for is therefore O(n), not O(n^2).

This is the same amortized argument as 4.4.9 and the monotonic stack. You will be asked for it.

The precondition nobody states ​

A window only works if shrinking reliably makes the window more valid.

With non-negative numbers, removing an element cannot increase the sum, so shrinking always moves you towards validity. Allow negative numbers and that breaks — removing an element might make the sum larger — and the window technique silently gives wrong answers. The replacement is prefix sums with a hash map.

Check this before reaching for a window. It is the single most common way to apply the pattern to a problem it does not fit.

The six problems ​

#ProblemThe one insight
4.6.1Best Time to Buy and Sell Stock ★Carry the cheapest price seen so far
4.6.2Longest Substring Without Repeating ★Shrink until the duplicate is gone
4.6.3Longest Repeating Character Replacement ★Valid when length − maxCount ≤ k
4.6.4Permutation in StringFixed-size window, compare letter counts
4.6.5Minimum Window Substring ★Count distinct requirements still unmet
4.6.6Sliding Window MaximumA monotonic deque keeps only possible winners

★ marks the Blind 75 subset.

The traps on this pattern ​

Recording the answer in the wrong place. Longest problems record after the shrink loop; shortest problems record inside it. Mixing them up gives answers that are subtly wrong on some inputs and right on others.

Off-by-one in the window length. It is right - left + 1, because both ends are included.

Slicing strings inside the loop. s[left:right+1] is O(n) and turns a linear solution quadratic. Track index pairs and slice once at the end.

Using list.pop(0) as a queue. It is O(n) in Python. Use collections.deque. JavaScript's Array.shift() has the same issue.

Applying a window where shrinking does not help. See the precondition above.

What the interviewer will push on ​

"Why is this O(n) when there is a nested loop?" The left pointer only moves forwards and never passes right, so it advances at most n times overall.

"Substring or subsequence?" Windows only do contiguous. If gaps are allowed, it is a different technique.

"Your maxCount in the replacement problem is never decreased — is that a bug?" No, and the argument is on 4.6.3. This is asked almost every time.

"What breaks if the array contains negative numbers?" Shrinking no longer reliably helps, so the window is invalid as a technique. Use prefix sums with a hash map instead.

One thing to volunteer: say which of the two shapes you are using before you write code. "This is a shortest-valid-window problem, so I shrink while valid and record inside the loop."

Recall

  • Windows solve contiguous longest and shortest problems. Subsequences with gaps are DP, not windows.
  • Longest: shrink while invalid, record after. Shortest: shrink while valid, record inside. Fixed size: no while at all.
  • Linear because both pointers only move forwards and left never passes right — at most n advances in total.
  • Window length is right − left + 1.
  • The precondition: shrinking must make the window more valid. Negative numbers break that and force prefix sums instead.
  • Track index pairs rather than slicing substrings inside the loop, or the solution goes quadratic.
  • For the maximum or minimum over a sliding range, use a monotonic deque — O(1) per step.

Next: 4.6.1 Best Time to Buy and Sell Stock — the simplest member, and the one that quietly introduces the idea behind dynamic programming.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet