Sliding Window Maximum Editorial

Practice Problem Link: Sliding Window Maximum

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an array of integers A and a number k which represents the size of the window. The window covers k elements and starts at the left end of the array. The window moves one index to the right at every step. You need to return an array with the max element inside the window at every step.

Naive Approach

We can use two nested loops to select the current window and then iterate in the current window to find the minimum element in that window and push it in the vector.

Analysis

• Time Complexity: O(n * k)
• Space Complexity: O(1)

Implementation

C++

vector<int> maxSlidingWindow(vector<int> &A, int k) {
    int n = A.size();
	vector<int> answer;
	for(int i = 0; i < n; i++) {
		int mx = INT_MIN;
		for(int j = i; j < i + k; j++) {
			mx = max(mx, A[j]);
		}
		answer.push_back(mx);
	}
	while(answer.size() > n - k + 1) {
		answer.pop_back();
	}
	return answer;
}

Java

class Solution {
	int[] maxSlidingWindow(int[] A, int k) {
	    int n = A.length;
		int[] answer = new int[n - k + 1];
		int pointer = 0;
		for(int i = 0; i < n; i++) {
			int mx = Integer.MIN_VALUE;
			for(int j = i; j < i + k; j++) {
				mx = Math.max(mx, A[j]);
			}
			answer[pointer] = mx;
			pointer++;
			if(pointer == n - k + 1)
				break;
		}
		return answer;
	}
}

Optimal Approach:

We can solve the problem optimally using a deque. The deque will have a capacity of k and will represent only the k elements that are present in the current window. Now observe that only those elements in the current window are of any value to us, which is greater than all the elements to the right of it, in the current window. We will traverse over the array elements in a single pass and maintain the useful elements in a sorted order using the deque. The front of the deque will have the largest element and the back will have the smallest valid element in the current window. Finally, after processing all the windows, print the maximum element.

Analysis:

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation:

C++

vector<int> maxSlidingWindow(vector<int> &a, int k) {
    int n = a.size();
	deque<int> dq(k);
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		while (dq.size() && a[i] >= a[dq.back()]) {
			dq.pop_back(); 
		}
		dq.push_back(i);
	}
	for (int i = k; i < n; i++){
		answer.push_back(a[dq.front()]);
		while(dq.size() && dq.front() <= i - k) {
			dq.pop_front();
		} 
		while(dq.size() && a[i] >= a[dq.back()]) {
			dq.pop_back();
		}
		dq.push_back(i);
	}
	answer.push_back(a[dq.front()]);
	return answer;
}

Java

class Solution {
	int[] maxSlidingWindow(int[] A, int k) {
	    if (A == null || A.length == 0 || k <= 0) {
			return new int[0]; 
		}
        final int N = A.length;
        if (k == 1) {
			return Arrays.copyOf(A, N);
		}
        int[] result = new int[N - k + 1];
        int idx = 0;
        Deque<Integer> deq = new ArrayDeque<>(k);
        for (int i = 0; i < N; i++) {
            if (!deq.isEmpty()  && i - deq.getFirst() == k) {
                deq.removeFirst(); 
            }
            while (!deq.isEmpty() && A[deq.getLast()] < A[i]) {
                deq.removeLast();
            }
            deq.addLast(i);
        
            if (i >= k - 1) {
                result[idx++] = A[deq.getFirst()];
            }
        }
        return result;
	}
}