Sliding Window

Here are some hint that triggers me to consider this algorithm

Note: A subarray is a contiguous non-empty sequence of elements within an array.

A sliding window is a pair of indices $(l, r)$ that bracket a contiguous subarray of the input. Instead of re-scanning every candidate window from scratch, we move the right end forward one step at a time and, whenever the window breaks some invariant, advance the left end just enough to restore it. Because each index only ever moves forward, the whole sweep runs in linear time — the cost of a random-access scan, but over windows instead of single elements.

The canonical instance is "maximum of every fixed-size window". With a monotonic deque we can answer each of the $n - k + 1$ windows in amortized constant time by popping any element that can no longer be the maximum (either because it has fallen off the left end, or because a larger element has arrived on the right).

The solve function below takes a single list [nums, k] and returns the list of window maxima.

Codes

This should be the section that should be filled first; it follows my naming convention and some standard coding. It should have at least runnable Python code so that I can copy and paste efficiently.

Python

Generic sliding-window template:

def slidingWindow(self, nums: List[int], Callable: condition):
    lo = 0
    res = 0
    for hi in range(len(nums)):
        condition('add',nums[hi])
        while condition('satisfied'):
            condition('remove',nums[lo])
            lo+=1
        res += lo
    return res

Maximum of every window of size $k$ with a monotonic deque:

from collections import deque

def solve(xs):
    """xs = [nums, k]. Return max of every contiguous window of size k."""
    nums, k = xs
    if k <= 0 or not nums:
        return []
    dq = deque()          # holds indices; values are decreasing
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

C++

#include <deque>
#include <vector>

std::vector<int> sliding_window_max(const std::vector<int>& nums, int k) {
    std::deque<int> dq;                 // indices, nums[dq] decreasing
    std::vector<int> out;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) out.push_back(nums[dq.front()]);
    }
    return out;
}

Example

Loading Python runner...

Description

Let's denote the length of the array by $n$.

What the sliding window algorithm does is that it maintains a window of elements that satisfies a certain condition. Then we can count the number of such windows or subarrays in total.

Runtime: $O(n \times condition)$

Memory: $O(n \times condition)$

Run time analysis

$O(n)$. Every index is pushed onto the deque exactly once and popped at most once, so the total work across the whole scan is proportional to $n$, independent of the window size $k$.

Space analysis

$O(k)$ auxiliary. The deque never holds more than $k$ indices at a time because anything older is evicted when it falls off the left end of the window. The output list is $O(n - k + 1)$.

Proof of correctness

We maintain two invariants just before processing index $i$:

1. The deque contains a strictly decreasing sequence of values $nums[dq[0]] > nums[dq[1]] > \dots$ at indices inside the window $[i - k + 1,\ i - 1]$.
2. Every index $j < i$ that is still inside the current window and whose value could ever be the maximum of some later window is in the deque.

The first invariant is restored by popping from the back while the back value is $\le nums[i]$: any index we discard is dominated by $i$ in every future window that contains both, so it can never again be a maximum. The second invariant is restored by popping from the front if the front index has fallen out of the window. After these two cleanups, the deque is decreasing and fully inside the current window, so its front index holds the maximum of the window ending at $i$. Reporting $nums[dq[0]]$ for $i \ge k - 1$ therefore yields the correct maximum for every window.

Extensions

Additional resource to consider and other possible algorithms that can be combined with it, with examples

Applications

This should be a list of problems that use the algorithm.

Counting subarrays

Problem 1 [Expected difficulty: 8]

count subarrays with score less than k

Intuition

Use multiplication directly

Solution

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        lo,res,n,cursum=0,0,len(nums),0
        for hi in range(n):
            cursum+=nums[hi]
            while cursum*(hi-lo+1)>=k:
                cursum-=nums[lo]
                lo+=1
            res+=hi-lo+1
        return res

If you like struggling yourself, you may solve this via prefix array, and wonder if that might be simpler, but that's actually slower. (I tried that first since it was noticed as "Hard".)

Problem 2 [Expected difficulty: 10]

count subarrays with fixed bounds

Intuition

Notice that any position with a number out of bounds will eliminate any choice of subarrays.

Solution

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int bp=-1,n=nums.size(),minI=-1,maxI=-1;
        long long res=0;
        for(int hi=0;hi<n;hi++){
            if (nums[hi]<minK || nums[hi]>maxK){
                bp=hi;
                continue;
            }
            if (nums[hi]==minK) minI=hi;
            if (nums[hi]==maxK) maxI=hi;
            if (minI>bp && maxI>bp) res+=min(minI,maxI)-bp;
            // cout<<lazylo<<" "<<lo<<" "<<hi<<":"<<minN<<" "<<maxN<<endl;
        }
        return res;
    }
};

Problem 3 [Expected difficulty: 12]

count of interesting subarrays

Intuition

We only care about when cnt%modulus==k , so we can create buckets to store those remainder terms on each visit of each number.

Consider the following cases, where 1 denotes that nums[i]%modulus==k and when the modulus is 3. Here, each entry of the table represents the number of arrays ending at index of the column j with modulus k.

k	1	0	1	1	1	0
2	0	0	1	2	1	1
0	1	1	2	1	2	2
1	0	1	0	1	2	3

Notice that on each index, we add the number k by one and when nums[i]%modulus==k We shift the entire column up by one.

And the number we are consistently checking is the sum row.

Solution

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n=nums.size(),cntb=0;
        long long res=0;
        unordered_map<int,int>b;
        for (int hi=0;hi<n;hi++){
            b[cntb]++;
            // shift adder
            if(nums[hi]%modulo==k) cntb=(cntb+modulo-1)%modulo;
            res+=b[(cntb+k)%modulo];
        }
        return res;
    }
};

References

This should be a list of references that I used to write the algorithm.

Some examples:

• cp-algorithms
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 17 (Amortized Analysis).
• cp-algorithms — Sliding window minimum/maximum