Not Frequent
0/13

# Sliding Window

Authors: Darren Yao, Benjamin Qi, Andrew Wang

### Prerequisites

Maintaining data over consecutive subarrays.

## Sliding Window

From CPH:

A sliding window is a constant-size subarray that moves from left to right through the array.

For each position of the window, we want to compute some information.

Focus Problem – read through this problem before continuing!

### Implementation

The most straightforward way to do this is to store an ordered set of integers representing the integers inside the window. If the window currently spans the range $i \dots j$, we observe that moving the range forward to $i+1 \dots j+1$ only removes $a_i$ and adds $a_{j+1}$ to the window. We can support these two operations and query for the minimum / maximum in the set in $\mathcal{O}(\log N)$.

Time Complexity: $\mathcal{O}(N\log N)$

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {    multiset<int> s;    vector<int> ret;    for(int i = 0; i < k; i++){        s.insert(nums[i]);    }    for(int i = k; i < nums.size(); i++){        ret.push_back(*s.rbegin());        s.erase(s.find(nums[i-k]));        s.insert(nums[i]);    }    ret.push_back(*s.rbegin());    return ret;}

Java

static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();static void add(int x) {    if(multiset.containsKey(x)) {        multiset.put(x, multiset.get(x) + 1);    } else {        multiset.put(x, 1);    }}static void remove(int x) {    multiset.put(x, multiset.get(x) - 1);

### Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESNormal
Show Tags

prefix-sums

CSESNormal
Show Tags

Sliding Window, Set

CSESHard
Show Tags

Sliding Window, Set

## With Two Pointers

In general, it is not required for the subarray to have constant size as long as both the left and right endpoints of the subarray only move to the right.

Focus Problem – read through this problem before continuing!

### Solution

C++

int n;set<int> s;int a[200000], ans;
int main() {    int r = -1;    cin >> n; F0R(i,n) cin >> a[i];    F0R(i,n) {        while (r < n-1 && !s.count(a[r+1])) s.insert(a[++r]);        ans = max(ans,r-i+1);        s.erase(a[i]);    }    cout << ans;}

Java

public class test{    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine());        StringTokenizer st = new StringTokenizer(br.readLine());        int a[] = new int[n];        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());        int r = -1;        HashSet<Integer> s = new HashSet<Integer>();        int ans = 0;

### Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CFEasyCheck CF
GoldEasy
Show Tags

Set, Sliding Window

External Sol
APIONormal
Show Tags

Sliding Window, Median

GoldNormal
Show Tags

Sliding Window

External Sol
PlatNormal
Show Tags

Sliding Window

External Sol
APIOHard
Show Tags

Sliding Window, DP

IOIHard
Show Tags

Sliding Window, Binary Search, DP

External Sol
IOIHard
Show Tags

Sliding Window, DP

External Sol

## Sliding Window Minimum in $\mathcal{O}(N)$

Focus Problem – read through this problem before continuing!

### Resources

Resources
cp-algomultiple ways to solve this

### Method 1 - Deque

Method 2 from cp-algo.

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {    deque<int> d;    vector<int> ret;    for(int i = 0; i < k; i++){        while(!d.empty() && nums[i] > nums[d.back()]){            d.pop_back();        }        d.push_back(i);    }    for(int i = k; i < nums.size(); i++){

Java

static ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {    ArrayList<Integer> ret = new ArrayList<Integer>();    ArrayDeque<Integer> d = new ArrayDeque<Integer>();    for (int i = 0; i < k; i++) {        while(!d.isEmpty() && nums[i] > nums[d.peekLast()]) {                d.pollLast();        }        d.addLast(i);    }    for (int i = k; i < nums.length; i++) {

### Method 2 - Two Stacks

Method 3 from cp-algo. Not as common but nice to know!

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

### Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
YSHardView Solution
Baltic OIHard

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Sliding Window!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.