Java Program to Solve Sliding Window Maximum Problem

Sliding Window Maximum problem is a question that is asked in different companies like Google, Amazon & Walmart. You will find the question in websites like LeetCode and InterviewBit.  

An array of integers A is given to us. We have a sliding window of size B which is moving from the left of the array to the right. Each time the window moves by one element to the right. We need to find the maximum element in each of these windows.

Suppose we have an array [1, 3 , 2, -4, 5] as input. Window size B is 3.
Current Window      Maximum Element
1,  3,  2                              3
3,  2 , -4                            3 
2, -4, 5                              5

To do this in O(n) time complexity, we will take the help of a deque. Within the deque we will store the index of the current window elements & they will be sorted by descending order of their values. So when we run a for loop, the first element of the deque would be the largest element of the previous window. We are then cleaning up any indexes from the deque which belong to previous window. If you see from the code below, any element in the deque can be added & removed only once. So time complexity for Sliding Window Maximum Problem would be O(n).


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public ArrayList<Integer> slidingMaximum(final List<Integer> A, int B) {
        ArrayList<Integer> results = new ArrayList<Integer>();
        if(B > A.size()){
            int slidingMaximum = 0;
            for(int a : A){
                if(slidingMaximum < a){
                    slidingMaximum = a;
                }
            }
            results.add(slidingMaximum);
            return results;
        }
        
        LinkedList<Integer> deque = new LinkedList<Integer>();
        
        for(int i=0; i<B; i++){
            while(!deque.isEmpty() && A.get(deque.getLast()) <= A.get(i)){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        
        for(int i=B; i<A.size(); i++){
            results.add(A.get(deque.getFirst()));
            while(!deque.isEmpty() && deque.getFirst() <= (i-B)){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && A.get(deque.getLast()) <= A.get(i)){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        results.add(A.get(deque.getFirst()));
        return results;
    }
}

Comments