PrevNext
Not Frequent
 0/17

Sliding Window

Author: Benjamin Qi

Contributors: Darren Yao, Andrew Wang, Chuyang Wang, Martin Lin

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 – try your best to solve this problem before continuing!

Implementation

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

Time Complexity: O(NlogN)\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 NameDifficultyTags
CSESNormal
Show TagsPrefix Sums, Sliding Window
CSESNormal
Show TagsSet, Sliding Window
CSESHard
Show TagsSet, Sliding Window

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 – try your best to solve 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;
}

Python

n = int(input().strip())
nums = [int(v) for v in input().split(" ")]
ans = -float("inf")
left, right = 0, 0
unique_songs = set()
while right < n:
# Notice that all the songs in unique_songs are unique in each iteration.
# We keep this property by shrinking the window before inserting nums[right].

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>();

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
GoldEasy
Show TagsSet, Sliding Window
ACEasy
Show TagsSliding Window
CSESEasy
Show Tags2P, Sliding Window
APIONormal
Show TagsMedian, Sliding Window
GoldNormal
Show TagsSliding Window
PlatinumNormal
Show TagsSliding Window
APIOHard
Show TagsDP, Sliding Window
IOIHard
Show TagsBinary Search, DP, Sliding Window
IOIHard
Show TagsDP, Sliding Window

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

Focus Problem – try your best to solve this problem before continuing!

Resources

Resources
cp-algo

multiple 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++) {
ret.push_back(nums[d.front()]);
if (!d.empty() && d.front() <= i - k) { d.pop_front(); }

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++) {
ret.add(nums[d.peekFirst()]);
if (!d.isEmpty() && d.peekFirst() <= i - k) { d.pollFirst(); }

Python

from typing import List
def maxSlidingWindow(self, nums: List[int], k: int) -> list[int]:
d = collections.deque()
def enqueue(i: int) -> None:
while d and nums[d[-1]] <= nums[i]:
d.pop()
d.append(i)

Method 2 - Two Stacks

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

We use two stacks s1s_1 and s2s_2 to simulate our maximum queue. Every time we add an element to it, we push the element itself and the maximum in stack s1s_1 after adding this element to s1s_1. To pop out the front element from our queue, we just pop the top element from s2s_2. Since elements in s1s_1 are stored in the order of how we added them, i.e. the last added element is at the top of s1s_1, we just have to pop all of them out and push them into the stack s2s_2 when s2s_2 is empty. After that, these elements in s2s_2 will be in reversed order, i.e. the first added element will be at the top of s2s_2, and we can pop them out as from normal stacks to simulate the dequeue operation of our queue. To find the maximum among all elements in our queue, we just have to return the maximum of both stacks, which is stored in the top element when we added it.

Then, we can solve the problem by removing the first element and adding a new element to the queue to simulate our sliding window. As each operation of our queue takes O(1)\mathcal{O}(1) time, and we add each of NN elements once, we get a time complexity of O(N)\mathcal{O}(N).

C++

struct MaxQueue {
/**
* For each pair<int, int> e, e.first is the value of the element and
* e.second is the maximum among all elements in that stack under element e.
*/
stack<pair<int, int>> s1, s2;
/**
* Get the maximum element in the MaxQueue.
* It is the maximum of both stacks which are stored in s.top().second.

Java

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MaxQueue q = new MaxQueue();
int n = nums.length;
int[] maxVals = new int[n - k + 1];
// Fill the queue with elements from the first window
for (int i = 0; i < k; i++) { q.enqueue(nums[i]); }
maxVals[0] = q.query();

Problems

StatusSourceProblem NameDifficultyTags
YSHard
Baltic OIHard

This section is not complete.

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

Module Progress:

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!

PrevNext