Sliding Window Technique
High ImportanceMaintain a moving contiguous window across arrays or strings to solve subarray/substring range queries in O(N) linear time, replacing redundant O(N²) or O(N·K) nested recalculations.
When to Use Sliding Window:
Key problem characteristics and signals indicating that this technique is the optimal choice.
Contiguous subarray or substring optimization problems requiring minimum/maximum length or sum matching a predicate.
Fixed-size window calculations, such as finding the maximum sum of any consecutive K elements or rolling average.
Dynamic condition constraints with frequency tracking, such as substring with at most K distinct characters or longest substring without repeating characters.
String anagram search, permutation matching, and character count comparisons over rolling slices.
Extremum tracking over moving intervals where a Monotonic Deque maintains the maximum/minimum in amortized O(1).
Prerequisite Rule: Sliding window strictly applies to contiguous sequences (subarrays or substrings). For non-contiguous subsequences or when negative values invalidate monotonicity, prefix sum or dynamic programming approaches are standard.
Example Problem — Maximum Sum Subarray of Size K
The benchmark interview problem demonstrating the transition from quadratic brute force to linear optimality.
Problem Statement
Given an array of integers arr[] and a positive integer K, find the maximum sum of any contiguous subarray of size K. Return the maximum sum achieved.
arr = [2, 1, 5, 1, 3, 2], K = 3
9 (Subarray: [5, 1, 3] at indices [2, 4])
Explanation: Subarrays of size K=3 are: [2, 1, 5] with sum 8, [1, 5, 1] with sum 7, [5, 1, 3] with sum 9, [1, 3, 2] with sum 6. The maximum sum among all windows is 9.
Naive Method — O(n · k) Time and O(1) Space
The baseline brute force approach recalculating candidates through nested loops.
The brute force approach calculates the sum of every possible contiguous subarray of size K from scratch by executing an inner loop of length K for every starting index.
def max_sub_array_of_size_k_naive(arr: list[int], k: int) -> int: n = len(arr) if n < k or k <= 0: return 0 max_sum = float('-inf') # Evaluate every window starting at index i for i in range(n - k + 1): current_sum = 0 for j in range(i, i + k): current_sum += arr[j] max_sum = max(max_sum, current_sum) return max_sumWhy Naive Fails in Production & Interviews
For an array with n = 10⁵ elements and k = 50,000, recalculating the sum of each window independently requires (n - k + 1) · k ≈ 2.5 × 10⁹ operations, causing Time Limit Exceeded (TLE). The fundamental flaw is that consecutive windows overlap by k - 1 elements, yet the naive approach throws away previous work and redundantly re-adds all elements from scratch.
Sliding Window Technique — O(n) Time and O(1) Space
The optimal strategy leveraging sliding window mechanics to achieve optimal time complexity.
By maintaining a moving contiguous window, we compute the sum of the first K elements once. As the window slides one position rightward, we subtract the outgoing element leaving on the left and add the incoming element entering on the right in O(1) time.
1. Compute Initial Window Sum: Sum the first K elements (indices 0 to K - 1). Initialize window_sum = sum(arr[0 ... K-1]) and max_sum = window_sum.
2. Slide Window Rightward: Iterate from index i = K up to n - 1. In each step, the active window spans [i - K + 1 ... i].
3. Subtract Outgoing Element: Subtract arr[i - K] (the element falling outside the left edge of the window) from window_sum in O(1).
4. Add Incoming Element: Add arr[i] (the new element entering the right edge of the window) to window_sum in O(1).
5. Update Global Extremum: Update max_sum = max(max_sum, window_sum). After one single linear pass, return max_sum.
Interactive Trace
Interactive Trace: Maximum Sum Subarray of Size K (arr = [2, 1, 5, 1, 3, 2], K = 3)
Interactive Trace: Maximum Sum Subarray of Size K (arr = [2, 1, 5, 1, 3, 2], K = 3)
arr = [2, 1, 5, 1, 3, 2], K = 3
9 (Subarray: [5, 1, 3] at indices [2, 4])
State Mutation Inspector
Decision & Invariant Action
Sum first K=3 elements: 2 + 1 + 5 = 8. This forms the baseline window [0..2].
Sliding Window Algorithm Code
Complete runnable solution in Python, C++, Java, and JavaScript.
def max_sub_array_of_size_k(arr: list[int], k: int) -> int: """ Standard Fixed-Size Sliding Window Template Time Complexity: O(N) | Space Complexity: O(1) """ n = len(arr) if n < k or k <= 0: return 0 window_sum = sum(arr[:k]) max_sum = window_sum for i in range(k, n): window_sum += arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) return max_sumHow does this work?
Algebraic Window Invariant & Why Overlap Elimination Drops Complexity to O(N)
Two consecutive windows share K - 1 identical elements. By reusing the previous sum and applying the rolling difference formula W[i+1] = W[i] - outgoing + incoming, each transition executes in exactly O(1) time.
1. Contiguous Overlap Principle
Consider two adjacent windows of size K: W1 = [arr[0], ..., arr[K-1]] and W2 = [arr[1], ..., arr[K]]. Both windows share arr[1], arr[2], ..., arr[K-1] in common (K - 1 identical elements). Recomputing their sum from scratch discards valuable precomputed work and wastes O(K) cycles.
2. The Rolling Difference Identity
Algebraically, Sum(W2) = Sum(W1) - arr[0] + arr[K]. Because addition and subtraction are associative and invertible operations, we transition between any two adjacent states using exactly 1 subtraction and 1 addition. The transition cost is strictly O(1) and completely independent of the window size K.
3. Strict Amortized Linear Bound
The window's right boundary enters each element exactly once (N operations total), while the left boundary leaves each element at most once (N operations total). Over the entire array of length N, the algorithm performs at most 2N operations, ensuring a bulletproof O(N) runtime regardless of whether K = 2 or K = 50,000.
4. Generalization to Frequency and Deque State
The sliding window principle extends beyond numeric sums: character frequency maps, bitmasks, and monotonic queues can all be maintained in O(1) amortized time by pairing right-boundary additions with left-boundary subtractions.
Core Pattern Variations & Blueprints
Explore the 3 structural variations that power all sliding window interview problems. Click each variation to expand its blueprint, interactive dry run, and implementation.
Window length stays constant at exactly K elements. We initialize the first K elements, then slide both left and right boundaries together by 1 step per iteration.
The Algorithmic Invariant
Window length is strictly K at every step. Window Sum = Previous Window Sum - outgoing + incoming in O(1).
Pointer Traversal Flow
[ 2 ] [ 1 ] [ 5 ] [ 1 ] [ 3 ] [ 2 ]
└──────────┬──────────┘
Window 0 (Sum = 8)
└──────────┬──────────┘
Window 1 (Sum = 7)
└──────────┬──────────┘
Window 2 (Sum = 9) ◄── Maximum!Worked Example: Maximum Sum Subarray of Size K (arr = [2, 1, 5, 1, 3, 2], K = 3)
arr = [2, 1, 5, 1, 3, 2], K = 3Step 1: Compute initial window [0..2] -> 2 + 1 + 5 = 8. Max sum = 8.
Step 2: Slide to [1..3] -> Subtract arr[0]=2, Add arr[3]=1 -> Sum = 8 - 2 + 1 = 7. Max sum remains 8.
Step 3: Slide to [2..4] -> Subtract arr[1]=1, Add arr[4]=3 -> Sum = 7 - 1 + 3 = 9. Max sum updated to 9.
Step 4: Slide to [3..5] -> Subtract arr[2]=5, Add arr[5]=2 -> Sum = 9 - 5 + 2 = 6. Max sum remains 9.
Interactive Dry Run Simulator
Fixed-Size Trace: Maximum Sum Subarray of Size K
arr = [2, 1, 5, 1, 3, 2], K = 3
Max Sum = 9
State Mutation Inspector
Decision & Invariant Action
Compute sum of initial window [2, 1, 5] = 8.
Production-Grade Implementation
def fixed_sliding_window(arr: list[int], k: int) -> int: """ Fixed-Size Window (Length = K) Time Complexity: O(N) | Space Complexity: O(1) """ n = len(arr) if n < k or k <= 0: return 0 window_sum = sum(arr[:k]) max_sum = window_sum for i in range(k, n): window_sum += arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) return max_sumLandmine to Avoid: Off-by-one window boundaries: subtracting arr[i - k + 1] instead of arr[i - k], or missing the initial window initialization loop before sliding.
Curated Practice Ladder
Master this pattern progressively through verified interview questions.
Create a free account to track progress and unlock your free practice set.
Premium also includes the full problem library, detailed solutions, hints, and advanced revision tools.
Already have an account? Log in
“Master the invariants,
and the solution
writes itself.”
