Problem Statement
Given an array of integers A. There is a sliding window of size K which is moving from the very left of the array to the very right.
You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. You have to find the maximum for each window.
Return an array C, where C[i] is the maximum value from A[i] to A[i+K-1].
Note: If k > length of the array, return 1 element with the max of the array.
Examples:
Input: A[] = {1, 3, -1, -3, 5, 3, 6, 7}, K = 3
Output: {3, 3, 5, 5, 6, 7}
Explanation:
| Window position | Max |
| [1 3 -1] -3 5 3 6 7 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 7 |
Input: A[] = {1, -1}, k = 1
Output: {1, -1}
Brute Force Approach
The simplest approach to solve this problem is to iterate over all possible sliding windows and find the maximum for each window.
There can be a total of N – K + 1 sliding window and there are K elements in each window.
Algorithm:
- Run a loop i from 0 to N – K + 1, denoting the current window.
- Initialise a variable max to INT_MIN to find the maximum value of each window.
- Run a nested loop from j from i to i + K to iterate over the elements of the current window and maximize max.
- Store the value of max for each window and return.
C++ Implementation
vector<int> SlidingWindowMaximum(int A[], int n, int K) {
if (n * K == 0){
return {};
}
vector<int> output(n - K + 1, 0);
for (int i = 0; i < n - K + 1; i++) {
int max = INT_MIN;
for(int j = i; j < i + K; j++)
max = max(max, A[j]);
output[i] = max;
}
return output;
}
Java Implementation
public int[] SlidingWindowMaximum(int[] A, int K) {
int n = nums.length;
if (n * K == 0) return new int[0];
int [] output = new int[n - K + 1];
for (int i = 0; i < n - K + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + K; j++)
max = Math.max(max, A[j]);
output[i] = max;
}
return output;
}
Python Implementation
def SlidingWindowMaximum(A, K):
n = len(nums)
if n * K == 0:
return []
return [max(A[i:i + K]) for i in range(n - K + 1)]
Time Complexity:O(N * K) where N is the size of the array A[].
Space Complexity:O(N – K + 1), as extra space is used.
Efficient Approach: Using Deque
The previous approach takes O(N * K) time, which would give a Time Limit Exceeded error for large values of K.
One of the ideas to reduce the time complexity could be to use a max heap, since the maximum element is always present at the top of the heap, but an insertion in a max heap of size K takes O(log K) time. Therefore, the time complexity becomes O(N log K), which is efficient. Can we reduce it further?
The idea is to use a deque i.e. double ended queue which performs the push() and pop() operations in O(1) constant time.
Algorithm:
- Initialise the first K elements of the array into the deque.
- Iterate over the input array and for each step:
- Consider only the indices of the elements in the current window.
- Pop-out all the indices of elements smaller than the current element, since their value will be less than the current element.
- Push the current element into the deque.
- Push the first element of the deque i.e. deque[0] into the output array.
C++ Code for Deque Method
vector<int> SlidingWindowMaximum(vector<int>& A, int K) {
deque<int> dq;
vector<int> ans;
for (int i=0; i<nums.size(); i++) {
if (!dq.empty() && dq.front() == i-K) dq.pop_front();
while (!dq.empty() && A[dq.back()] < A[i])
dq.pop_back();
dq.push_back(i);
if (i>=K-1) ans.push_back(nums[dq.front()]);
}
return ans;
}
Java Code for Deque Method
ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
int [] A;
public void clean_deque(int i, int K) {
if (!deq.isEmpty() && deq.getFirst() == i - K)
deq.removeFirst();
while (!deq.isEmpty() && nums[i] > A[deq.getLast()]){
deq.removeLast();
}
}
public int[] SlidingWindowMaximum(int[] A, int K) {
int n = A.length;
if (n * B=K == 0) return new int[0];
if (K == 1) return A;
this.A = A;
int max_idx = 0;
for (int i = 0; i < K; i++) {
clean_deque(i, K);
deq.addLast(i);
if (A[i] > A[max_idx]) max_idx = i;
}
int [] output = new int[n - K + 1];
output[0] = A[max_idx];
for (int i = K; i < n; i++) {
clean_deque(i, K);
deq.addLast(i);
output[i - K + 1] = A[deq.getFirst()];
}
return output;
}
Python Code for Deque Method
from collections import deque
def SlidingWindowMaximum(A, K):
n = len(A)
if n * K == 0:
return []
if K == 1:
return A
def clean_deque(i):
if deq and deq[0] == i - K:
deq.popleft()
while deq and A[i] > A[deq[-1]]:
deq.pop()
deq = deque()
max_idx = 0
for i in range(B):
clean_deque(i)
deq.append(i)
if A[i] > A[max_idx]:
max_idx = i
output = [A[max_idx]]
for i in range(K, n):
clean_deque(i)
deq.append(i)
output.append(A[deq[0]])
return output
Time Complexity:O(N) where N is the size of the array A[].
Space Complexity:O(N), as extra space is used.
Dynamic Programming Approach
The problem can be solved using Dynamic Programming. The approach is to divide the given array into different blocks each containing K elements. Let us understand the illustration with the below example.
A[] = {1, 3, -1, -3, 5, 3, 6, 7}
K = 3
The given array has been divided into parts, each containing K elements. SInce, the size of the array is not divisible by K, the last block contains elements less than K.
Two elements can be placed into two different sliding windows, while iterating as follows:
To solve problem 1, consider an auxiliary array left[] which denotes the maximum element obtained so far until index j.
Similarly to solve problem 2, consider an auxiliary array right[] which denotes the maximum element obtained so far until index j.
Now, since we have obtained all the maximum integers uptil index i from both directions, the maximum element in the sliding window from index i to index j is max(left[i], right[i]).
Algorithm:
- Construct an array left[], which contains the maximum element till index i iterating from left to right.
- Construct an array right[], which contains the maximum element till index i iterating from right to left.
- For each window size of N – K + 1, the maximum element will be max(left[i], right[N – i + 1]).
C++ Code for DP Approach
vector<int> SlidingWindowMaximum(vector<int>& A, int K) {
deque<int> dq;
vector<int> ans;
for (int i=0; i<nums.size(); i++) {
if (!dq.empty() && dq.front() == i-K) dq.pop_front();
while (!dq.empty() && A[dq.back()] < A[i])
dq.pop_back();
dq.push_back(i);
if (i>=K-1) ans.push_back(nums[dq.front()]);
}
return ans;
}
Java Code for DP Approach
public int[] SlidingWindowMaximum(int[] A, int K) {
int n = A.length;
if (n * K == 0) return new int[0];
if (K == 1) return nums;
int [] left = new int[n];
left[0] = nums[0];
int [] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
if (i % K == 0) left[i] = nums[i];
else left[i] = Math.max(left[i - 1], A[i]);
int j = n - i - 1;
if ((j + 1) % K == 0) right[j] = A[j]; // block_end
else right[j] = Math.max(right[j + 1], A[j]);
}
int [] output = new int[n - K + 1];
for (int i = 0; i < n - K + 1; i++)
output[i] = Math.max(left[i + K - 1], right[i]);
return output;
}
Python Code for DP Approach
def SlidingWindowMaximum(A, K):
n = len(A)
if n * K == 0:
return []
if K == 1:
return A
left = [0] * n
left[0] = A[0]
right = [0] * n
right[n - 1] = A[n - 1]
for i in range(1, n):
# from left to right
if i % k == 0:
left[i] = A[i]
else:
left[i] = max(left[i - 1], A[i])
j = n - i - 1
if (j + 1) % K == 0:
right[j] = A[j]
else:
right[j] = max(right[j + 1], A[j])
output = []
for i in range(n - K + 1):
output.append(max(left[i + K - 1], right[i]))
return output
Time Complexity:O(N) where N is the size of the array A[].
Space Complexity:O(N), as extra space is used.
Practice Questions:
Frequently Asked Questions
What is the time complexity of finding maximum for each window of size K
The time complexity is O(N) using a dynamic programming approach.
Can we use a heap to solve the problem?
Yes, a max heap can be used to solve the problem, but in that case, the time complexity would be O(N log K), since insertion in a max heap takes log(K) time. Here K denotes the size of the sliding window.
