PrevNext
Not Frequent
 0/15

Sliding Window

Authors: Darren Yao, Benjamin Qi, Andrew Wang

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 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 – 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 NameDifficultyTags
CFEasy
GoldEasy
Show TagsSet, Sliding Window
APIONormal
Show TagsMedian, Sliding Window
GoldNormal
Show TagsSliding Window
PlatNormal
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 – read through 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++){

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 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