Algorithms
Sliding Window (Intro)
Difficulty: Beginner
To find the longest substring of s with no repeated characters, the brute-force approach checks every substring in O(n^3) time. The sliding-window solution touches each character at most twice and runs in O(n): extend a right pointer...
Sliding Window (Intro)
To find the longest substring of s with no repeated characters, the brute-force approach checks every substring in O(n^3) time. The sliding-window solution touches each character at most twice and runs in O(n): extend a right pointer until a duplicate appears, then advance a left pointer until the duplicate is gone, repeating until the right pointer falls off the end.
Sliding Window (Intro) turns that idea into two reusable templates. The fixed-size window slides a range of length k across the array and updates the running sum or count by adding the new right element and removing the old left element, never recomputing from scratch. The variable-size window expands the right edge while a condition holds and shrinks the left edge to restore that condition, tracking the window's contents with a hash map or counter. You will apply both to maximum-sum subarray of size k, longest substring without repeating characters, minimum window substring, and longest substring with at most k distinct characters.
In Two Pointers (Intro), you used coordinated indices to walk an array linearly. Hash Map (Dictionary) Basics gave you the O(1) lookup and update that lets a window track its own contents efficiently. Sliding window combines both: two indices and one hash map.
From here you turn to Recursion Fundamentals, which trades sequential index movement for self-similar subproblems.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain how a sliding window avoids redundant computation by reusing work from the previous window position.
Implement a fixed-size sliding window to find the maximum sum of k consecutive elements.
Implement a variable-size sliding window to find the longest substring without repeating characters.
Trace window expansion and contraction step by step, tracking window boundaries and state.
Identify problems that are solvable with sliding window by recognizing contiguous subarray/substring clues.
Analyze the time and space complexity of sliding window solutions.
Why This Matters
01
Sliding window solves an entire class of contiguous subarray and substring problems in O(n) instead of the brute-force O(n^2) or O(n^3).
02
It is one of the most commonly tested interview patterns — roughly 10-15% of medium-difficulty array and string problems use it.
03
The technique builds directly on the two-pointer foundation, extending it from two-element lookups to variable-width ranges.
04
Real-world applications include streaming data analysis, network throughput monitoring, and text-processing algorithms.
Key Terms
7 terms you'll encounter in this lesson
Sliding window
A technique that maintains a contiguous subarray or substring defined by left and right boundaries, sliding the boundaries to process all valid ranges in O(n) time.
Fixed-size window
A window of constant size k that slides one position at a time. The new window adds one element on the right and removes one on the left.
Variable-size window
A window whose size changes dynamically. The right boundary expands to include more elements; the left boundary contracts to restore a constraint.
Window state
Auxiliary data (sum, count map, max value) maintained as the window slides, updated incrementally rather than recomputed from scratch.
Contiguous subarray
A sequence of elements that appear consecutively in the array with no gaps — the defining characteristic of problems suited for sliding window.
Shrink (contract)
Moving the left boundary of a variable-size window rightward to reduce the window size, typically to restore a violated constraint.
Expand
Moving the right boundary of a window rightward to include a new element, growing the window.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Sliding window works on non-contiguous subsequences"
Sliding window only works on contiguous subarrays or substrings. If the problem asks about non-contiguous subsequences (like 'longest increasing subsequence'), sliding window does not apply — use dynamic programming instead.
"A fixed-size window needs to recompute the sum from scratch each time it slides"
The whole point of sliding window is incremental updates. When the window slides by one position, subtract the element leaving on the left and add the element entering on the right. This gives O(1) per slide instead of O(k).
"Variable-size window is O(n^2) because the left pointer can move many times"
Each element is added to the window at most once (when right moves) and removed at most once (when left moves). Over the entire algorithm, left moves at most n times total, so the overall time is O(n), not O(n^2).