Sliding Window
The sliding window technique is a powerful approach for solving problems that involve contiguous subarrays or substrings. By maintaining a window that slides across the data, it reduces brute-force quadratic solutions down to linear time, making it one of the most frequently tested patterns in coding interviews.
How Sliding Window Works
The sliding window technique maintains a window — a contiguous range of elements defined by two pointers (or indices) — and slides it across an array or string. Instead of recalculating results from scratch for every possible subarray, the window incrementally updates its state as it moves, adding the new element entering the window and removing the element leaving it.
There are two main variants of the sliding window:
- Fixed-size window: The window size
kis predetermined. As the window slides one position to the right, we add the new rightmost element and remove the old leftmost element. A classic example is finding the maximum sum subarray of size k. - Variable-size window: The window expands and contracts dynamically based on a condition. We expand the right boundary to include more elements and shrink the left boundary when a constraint is violated. Examples include the longest substring without repeating characters and the minimum window substring.
Maximum sum subarray of size k: Given an array of integers and a window size k, find the subarray of length k with the largest sum. The brute-force approach sums every possible subarray of size k in O(n × k) time. With a sliding window, we compute the first window's sum, then slide the window by subtracting the element leaving the window and adding the new element — reducing time to O(n).
Longest substring without repeating characters: Use a variable-size window with a hash set tracking characters in the current window. Expand the right pointer to add characters; when a duplicate is found, shrink from the left until the window is valid again. This runs in O(n) time.
Minimum window substring: Given a string s and a target string t, find the smallest substring of s that contains all characters of t. Expand the right pointer until all target characters are covered, then shrink from the left to minimize the window size while maintaining coverage.
The key insight behind sliding window is that by leveraging the overlap between consecutive windows, we avoid redundant computation and achieve O(n) time complexity for problems that would otherwise require O(n2) or worse.
Interactive Visualization
Watch the sliding window technique in action on the maximum sum subarray of size k problem. The highlighted region shows the current window, and the running sum updates as the window slides across the array.
Code Implementation
Below is the implementation for finding the maximum sum subarray of size k using the sliding window technique. The window slides across the array in a single pass, maintaining a running sum by adding the incoming element and subtracting the outgoing element.
def max_sum_subarray(arr, k):
"""Return the maximum sum of any contiguous subarray of size k."""
n = len(arr)
if n < k:
return -1
# Compute the sum of the first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window from left to right
for i in range(k, n):
window_sum += arr[i] - arr[i - k] # Add incoming, remove outgoing
max_sum = max(max_sum, window_sum)
return max_sum
# Example usage
nums = [2, 1, 5, 1, 3, 2]
k = 3
result = max_sum_subarray(nums, k)
print(f"Max sum of subarray of size {k}: {result}") # Output: 9
public class SlidingWindow {
/**
* Returns the maximum sum of any contiguous subarray of size k.
*/
public static int maxSumSubarray(int[] arr, int k) {
int n = arr.length;
if (n < k) return -1;
// Compute the sum of the first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// Slide the window from left to right
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k]; // Add incoming, remove outgoing
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {2, 1, 5, 1, 3, 2};
int k = 3;
int result = maxSumSubarray(nums, k);
System.out.println("Max sum of subarray of size " + k + ": " + result); // Output: 9
}
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* Returns the maximum sum of any contiguous subarray of size k.
*/
int maxSumSubarray(const vector<int>& arr, int k) {
int n = static_cast<int>(arr.size());
if (n < k) return -1;
// Compute the sum of the first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// Slide the window from left to right
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k]; // Add incoming, remove outgoing
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
int main() {
vector<int> nums = {2, 1, 5, 1, 3, 2};
int k = 3;
int result = maxSumSubarray(nums, k);
cout << "Max sum of subarray of size " << k << ": " << result << endl; // Output: 9
return 0;
}
Complexity Analysis
The sliding window technique processes each element at most twice (once when it enters the window and once when it leaves), resulting in linear time complexity. Only a constant number of variables are needed to track the window state, so space usage is minimal.
| Case | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Best | O(n) | O(1) | The window slides across the entire array in a single pass |
| Average | O(n) | O(1) | Each element is added and removed from the window exactly once |
| Worst | O(n) | O(1) | Even in the worst case, the window performs a single linear scan |
Compared to the brute-force approach that examines all O(n × k) subarrays, the sliding window technique is a significant improvement. For variable-size windows (e.g., longest substring without repeating characters), space may increase to O(min(n, m)) where m is the character set size, but time remains O(n).
Quiz
Test your knowledge of the sliding window technique with these questions.
Q1. What is the main advantage of the sliding window technique over the brute-force approach?
Q2. Given the array [4, 2, 1, 7, 8, 1, 2, 8, 1, 0] and k = 3, what is the maximum sum of a subarray of size 3?
Q3. Which of the following problems is best solved with a variable-size sliding window?
Q4. In a fixed-size sliding window of size k, what happens at each step as the window moves one position to the right?
Q5. What is the time complexity of finding the minimum window substring (smallest substring of s containing all characters of t)?