Home » Technical Interview Questions » Array Interview Questions » Sliding Window Maximum

# Sliding Window Maximum

In Sliding Window Maximum problem we have given an array nums, for each contiguous window of size k, find the maximum element in the window.

## Example

Input
nums[] = {1,3,-1,-3,5,3,6,7} k = 3
Output
{3,3,5,5,6,7}

## Naive Approach for Sliding Window Maximum

For every contiguous window of size k, traverse in the window and find the maximum element.

1. Run a loop from index 0 to (size of array – k – 1)
2. Run another nested loop from index i to (i + k)
3. Nested loop represents a window, find the maximum value inside the nested loop
4. The maximum value found above is the current window’s maximum value.
5. Repeat above steps to find all the maximums

Time Complexity = O(n * k)
Space Complexity = O(1)

### JAVA Code

```public class Naive {
private static int[] maxSlidingWindow(int[] nums, int k) {
int ans[] = new int[nums.length - k + 1];
// Traverse all the windows one by one
for (int i = 0; i < nums.length - k + 1; i++) {
// Initialise max as -infinite
int max = Integer.MIN_VALUE;
// Traverse the current window and find the maximum
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
// assign the current ans as maximum
ans[i] = max;
}
return ans;
}

public static void main(String[] args) {
// Example
int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int max[] = maxSlidingWindow(nums, k);
// Print the maximums
for (int i = 0; i < max.length; i++) {
System.out.print(max[i] + " ");
}
}
}```
`3 3 5 5 6 7`

### C++ Code

```#include<bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
vector<int> ans;
// Traverse all the windows one by one
for (int i = 0; i < n - k + 1; i++) {
// Initialise max as -infinite
int max = INT_MIN;
// Traverse the current window and find the maximum
for (int j = i; j < i + k; j++) {
max = std::max(max, nums[j]);
}
// assign the current ans as maximum
ans.push_back(max);
}
return ans;
}

int main() {
// Example
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
// Print the maximums
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
return 0;
}```
`3 3 5 5 6 7`

## Optimal Approach for Sliding Window Maximum

Store the first k elements in a self balancing BST, the largest element in the BST gives the maximum element for the first window.
For the remaining subarrays, remove the first element of the previous window from self balancing BST and add the current element, the largest element again returns the maximum element in the current window.
To handle the case of repeated elements store element vs frequency in the BST.

READ  Maximum length subsequence with difference between adjacent elements as either 0 or 1

Time Complexity = O(n log(k))
Space Complexity = O(k)

### JAVA Code

```import java.util.TreeMap;

public class Optimal {
private static int[] maxSlidingWindow(int[] nums, int k) {
int ans[] = new int[nums.length - k + 1];
TreeMap<Integer, Integer> map = new TreeMap<>();
// Store the first k elements and their frequencies in a self balancing BST
for (int i = 0; i < k; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Largest value of BST gives the first maximum
ans[0] = map.lastKey();
int index = 1;
// Traverse the remaining elements
for (int i = k; i < nums.length; i++) {
// Remove first element of previous window from BST
int freq = map.get(nums[i - k]);
if (freq == 1) {
map.remove(nums[i - k]);
} else {
map.put(nums[i - k], freq - 1);
}

// Add current element to BST
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}

// Current asnwer is maximum value in BST
ans[index++] = map.lastKey();
}

return ans;
}

public static void main(String[] args) {
// Example
int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int max[] = maxSlidingWindow(nums, k);
// Print the maximums
for (int i = 0; i < max.length; i++) {
System.out.print(max[i] + " ");
}
}
}```
`3 3 5 5 6 7`

### C++ Code

```#include<bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
vector<int> ans;
map<int, int> eleFreq;
// Store the first k elements and their frequencies in a self balancing BST
for (int i = 0; i < k; i++) {
std::map<int, int>::iterator itr;
itr = eleFreq.find(nums[i]);
if (itr == eleFreq.end()) {
eleFreq.insert(make_pair(nums[i], 1));
} else {
itr->second++;
}
}
ans.push_back(eleFreq.rbegin()->first);
for (int i = k; i < n; i++) {
// Remove first element of previous window from BST
std::map<int, int>::iterator itr = eleFreq.find(nums[i - k]);
if (itr->second > 1) {
itr->second--;
} else {
eleFreq.erase(itr->first);
}

// Add current element to BST
itr = eleFreq.find(nums[i]);
if (itr == eleFreq.end()) {
eleFreq.insert(make_pair(nums[i], 1));
} else {
itr->second++;
}

// Current answer is maximum value in BST
ans.push_back(eleFreq.rbegin()->first);
}
return ans;
}

int main() {
// Example
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
// Print the maximums
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
return 0;
}```
`3 3 5 5 6 7`

References

READ  Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions