Introduction to Sliding Window
Learn how to turn O(N²) brute-force solutions into O(N) by maintaining a dynamic window of elements.
Examples
The answer is "abc", with the length of 3.
The answer is "b", with the length of 1.
What is the Sliding Window Technique?
The Sliding Window is a technique used to perform operations on a specific subset of data (a window) that moves across a larger dataset (usually an array or string).
Imagine looking at a long train through a small rectangular frame. As the train moves, you see different parts of it, but the size of your frame remains the constant (or expands/contracts). This allows us to process data sequentially without having to re-calculate everything from scratch for every subarray.
The Motivation: Longest Substring
Let's learn this with a classic problem: Longest Substring Without Repeating Characters.
"Given a string
s, find the length of the longest substring that contains no duplicate characters."
Example: s = "abcabcbb"
abc(Length 3) - Validabca(Length 4) - Invalid ('a' repeats)bcabc...
How do we find the maximum length efficiently?
Attempt 1: Brute Force (Why it fails)
The naive approach is to check every possible substring.
- Start at index 0 ('a'). Check subtr: 'a', 'ab', 'abc', 'abca'...
- Start at index 1 ('b'). Check subtr: 'b', 'bc', 'bca'...
The Problem:
- Time Complexity: O(N^3) or O(N^2) depending on implementation.
- Redundant Work: When checking 'abc' then 'abcd', we re-scan 'abc' unnecessarily. We should just asking: "Can we add 'd'?"
When should I use Sliding Window?
Pattern Recognition Triggers:
Use this technique when:
- Contiguous: The problem asks for a contiguous subarray or substring.
- Running Calculation: You need to calculate something (sum, average, count, max length) over a subset.
- Constraints: The input size is large (e.g., 10^5), requiring an O(N) solution.
- Keywords: "Longest", "Shortest", "Maximum Sum", "Minimum Length".
The Intuition: Expand and Contract
Instead of starting from scratch, let's treat the substring as a growing and shrinking window.
The Algorithm:
- Expand (Right): Extend the window by adding elements one by one.
- Validate: Check if the window is currently valid (e.g., no duplicates).
- Contract (Left): If invalid, shrink the window from the left until it becomes valid again.
- Update: Keep track of the best solution found during valid states.
Interactive Walkthrough
Initializing...
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.