Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Sliding Window

When a problem asks about a contiguous subarray or substring — "longest", "shortest", "maximum sum of size k", "at most k distinct" — a sliding window usually turns an O(n²) or O(n³) brute force into O(n).

The window is the range [left, right]. Instead of recomputing everything for every range, you add the element entering on the right and remove the one leaving on the left.

Type 1: fixed-size window

Maximum sum of any subarray of size k.

int maxSumK(vector<int>& a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int r = k; r < a.size(); r++) {
        sum += a[r] - a[r - k];       // add new, remove old
        best = max(best, sum);
    }
    return best;
}

Type 2: variable-size window

Grow the window with right; while the window breaks the rule, shrink it with left.

Template

int left = 0, best = 0;
for (int right = 0; right < n; right++) {
    add(a[right]);                    // expand
    while (windowIsInvalid()) {       // shrink until valid again
        remove(a[left]);
        left++;
    }
    best = max(best, right - left + 1);
}

Longest substring without repeating characters

int lengthOfLongestSubstring(string s) {
    vector<int> cnt(256, 0);
    int left = 0, best = 0;
    for (int right = 0; right < s.size(); right++) {
        cnt[s[right]]++;
        while (cnt[s[right]] > 1) cnt[s[left++]]--;
        best = max(best, right - left + 1);
    }
    return best;
}

Smallest subarray with sum ≥ target (positive numbers)

int minSubArrayLen(int target, vector<int>& a) {
    int left = 0, sum = 0, best = INT_MAX;
    for (int right = 0; right < a.size(); right++) {
        sum += a[right];
        while (sum >= target) {
            best = min(best, right - left + 1);
            sum -= a[left++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

Longest vs shortest

Asked Update the answer…
Longest valid window after shrinking (the window is valid again)
Shortest valid window inside the shrinking loop (while it is still valid)

"Exactly K" trick

Count of subarrays with exactly K distinct = atMost(K) − atMost(K − 1), where atMost is a normal variable window.

When the window does NOT work

The window needs this property: making the window bigger never makes it "more valid" in the wrong direction (monotonic). With negative numbers, "sum ≥ target" is no longer monotonic — use prefix sum + hash map instead (see the Hashing note).

Sliding window maximum (monotonic deque)

Keep indices in a deque with decreasing values; the front is the maximum of the current window. O(n).

vector<int> maxSlidingWindow(vector<int>& a, int k) {
    deque<int> dq; vector<int> ans;
    for (int i = 0; i < a.size(); i++) {
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();     // out of the window
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();  // smaller ones are useless
        dq.push_back(i);
        if (i >= k - 1) ans.push_back(a[dq.front()]);
    }
    return ans;
}

Classic problems

Problem Window
Max sum subarray of size K fixed
Longest substring without repeating characters variable + map
Longest substring with at most K distinct characters variable + map
Minimum size subarray sum variable (shortest)
Permutation in string / find all anagrams fixed + count array
Minimum window substring variable (shortest) + counts
Fruits into baskets / max consecutive ones III variable
Sliding window maximum fixed + deque

Practise them in the Sliding Window section.

Interview one-liners

More DSA notes