PrevNext
Not Frequent
 0/16

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)O(\log N).

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

C++

1vector<int> maxSlidingWindow(vector<int>& nums, int k) {
2 multiset<int> s;
3 vector<int> ret;
4 for(int i = 0; i < k; i++){
5 s.insert(nums[i]);
6 }
7 for(int i = k; i < nums.size(); i++){
8 ret.push_back(*s.rbegin());
9 s.erase(s.find(nums[i-k]));
10 s.insert(nums[i]);

Java

1static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();
2static void add(int x) {
3 if(multiset.containsKey(x)) {
4 multiset.put(x, multiset.get(x) + 1);
5 } else {
6 multiset.put(x, 1);
7 }
8}
9static void remove(int x) {
10 multiset.put(x, multiset.get(x) - 1);

Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESNormal
Show Tags

prefix-sums

View Solution
CSESNormalView Solution
CSESHardView Solution

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

1int n;
2set<int> s;
3int a[200000], ans;
4
5int main() {
6 int r = -1;
7 cin >> n; F0R(i,n) cin >> a[i];
8 F0R(i,n) {
9 while (r < n-1 && !s.count(a[r+1])) s.insert(a[++r]);
10 ans = max(ans,r-i+1);

Java

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

Problems

StatusSourceProblem NameDifficultyTagsSolution
CFEasyCheck CF
GoldEasy
Show Tags

Set, Sliding Window

External Sol
APIONormal
Show Tags

Sliding Window, Median

View Solution
GoldNormal
Show Tags

Sliding Window

External Sol
APIONormal
Show Tags

Sliding Window, DP

Check DMOJ
PlatHard
Show Tags

Sliding Window

External Sol
IOIHard
Show Tags

Sliding Window, Binary Search, DP

External Sol
IOIHard
Show Tags

Sliding Window, DP

External Sol

Sliding Window Minimum in O(N)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++

1vector<int> maxSlidingWindow(vector<int>& nums, int k) {
2 deque<int> d;
3 vector<int> ret;
4 for(int i = 0; i < k; i++){
5 while(!d.empty() && nums[i] > nums[d.back()]){
6 d.pop_back();
7 }
8 d.push_back(i);
9 }
10 for(int i = k; i < nums.size(); i++){

Java

1static ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
2 ArrayList<Integer> ret = new ArrayList<Integer>();
3 ArrayDeque<Integer> d = new ArrayDeque<Integer>();
4 for (int i = 0; i < k; i++) {
5 while(!d.isEmpty() && nums[i] > nums[d.peekLast()]) {
6 d.pollLast();
7 }
8 d.addLast(i);
9 }
10 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.

Feel free to file a request to complete this using the "Contact Us" button.

Problems

StatusSourceProblem NameDifficultyTagsSolution
YSHardView Solution
Baltic OIHard

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Module Progress:

Give Us Feedback on Sliding Window!

PrevNext