Lesson 5 · Core algorithms

Sliding Window Technique

Sliding Window is a subset of two pointers used to track a contiguous subset of elements. Instead of recalculating a property (like a sum) for every possible window, it updates the property by removing the element leaving the window and adding the element entering it.

Fixed-size windows

When a problem asks for a metric across a specific length K, initialize the window for the first K elements. Then, slide the window one element at a time to the right.

To slide, subtract the contribution of the element that just dropped out of the left side, and add the contribution of the element that just entered on the right side.

Maintain size strictly at K
Initialization step calculates first window
Slide step performs constant-time updates

Variable-size windows

For problems asking for the 'longest' or 'shortest' subarray that meets a condition, the window size must grow and shrink dynamically.

Expand the right boundary to include new elements until the condition is violated. Then, shrink the left boundary until the condition is satisfied again, recording the optimal window size seen along the way.

Right pointer expands to find valid windows
Left pointer shrinks to restore validity
Track max/min length during the valid state

Key reference

Terms, operations, and practical uses

Core vocabulary

WindowA contiguous sequence of elements in an array or string bounded by two indices (left and right).
Fixed SizeA window where the distance between the left and right pointers remains exactly K.
Dynamic SizeA window that grows or shrinks as needed to satisfy a particular condition.

Operations

ExpandIncreasing the window size by moving the right pointer and including a new element in the state.
ShrinkDecreasing the window size by moving the left pointer and removing its element from the state.
State UpdateModifying the running metric (sum, product, frequency map) in O(1) time when the window boundaries change.

Data structures

Hash Map / DictionaryUsed to keep track of character frequencies or counts of elements currently inside the window.
Frequency ArrayA fixed-size array (like int[128]) often used instead of a Hash Map for ASCII string problems to improve speed.
DequeA double-ended queue used in monotonic sliding window problems (like finding the maximum in every window of size K).

Code example

Maximum sum of any contiguous subarray of size 3

def max_sum(arr, k):
    window_sum = sum(arr[:k])
    max_val = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_val = max(max_val, window_sum)
    return max_val
print(max_sum([2, 1, 5, 1, 3, 2], 3), '(from [5, 1, 3])')

int maxSum(vector<int>& arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxVal = windowSum;
    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        maxVal = max(maxVal, windowSum);
    }
    return maxVal;
}

static int maxSum(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxVal = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxVal = Math.max(maxVal, windowSum);
    }
    return maxVal;
}

Inputarray = [2, 1, 5, 1, 3, 2], k = 3

Output9 (from [5, 1, 3])

Example

Run the example step by step

Output

State tracking

To know if a window is 'valid', you usually need auxiliary data structures. Hash maps are commonly used to track the frequencies of characters or numbers currently inside the window.

Keeping the state updated in O(1) time as elements enter and leave is crucial; otherwise, the O(N) performance of the sliding window is lost.

Use arrays for ASCII character counts
Use Hash Maps for sparse or arbitrary counts
Track a 'count' variable to avoid scanning the map

Identifying window problems

Keywords that suggest a sliding window approach include 'contiguous', 'subarray', 'substring', and asking for a 'maximum', 'minimum', or 'longest' property.

If a problem asks for subsequences (which are not contiguous) or involves negative numbers in a sum-based problem, sliding window may not apply, and dynamic programming or prefix sums might be needed.

Look for 'contiguous'
Verify elements are strictly positive if summing
Consider prefix sums as an alternative