Problem

You are given an array of integers nums, 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 k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Sometimes k is also denoted as w.

Example

Example

Input: nums = [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

Solution

There are a couple of solutions possible for this problem, lets look at them.

Method 1 - Brute Force

An O(n*w) bruteforce solution would be to do go through each of the element of the array and find minimum of w elements from the current position to the right.

Code

Java
public int[] maxSlidingWindow(int[] nums, int k) {
	int j, max;
	int n = nums.length;
	int[] ans = new int[nums.length - k + 1];

	for (int i = 0; i <= n - k; i++) {
		max = Integer.MIN_VALUE;

		for (j = 0; j < k; j++) {
			max = Math.max(max, nums[j + i]);
		}

		ans[i] = max;
	}

	return ans;
}

Method 2 - Using Max Heap - but wrong approach ❌

This approach, even though looks legitimate will not work.

This will not work

If you closely observe the way we calculate the maximum in each w-sized subarray, you will notice that we’re doing repetitive work in the inner loop. Let’s understand it with an example:

Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3

For the above example, we first calculate the maximum in the subarray {1, 2, 3}, then we move on to the next subarray {2, 3, 1} and calculate the maximum. Notice that, there is an overlap in both the subarrays:

Subarray 1 - [1, 2, 3]
Subarray 2 - [2, 3, 1]

So we’re calculating the maximum in the overlapping part (2, 3) twice. We can utilize the sliding window technique to save us from re-calculating the maximum in the overlapping subarray and improve the run-time complexity.

In the sliding window technique, we consider each k-sized subarray as a sliding window. To calculate the maximum in a particular window (2, 3, 1), we utilize the calculation done for the previous window (1, 2, 3).

Since we want to utilize the calculation from the previous window, we need a way to store the calculation for the previous window. We’ll use a PriorityQueue to store the elements of the sliding window in decreasing order (maximum first).

Code

Java
public int[] maxSlidingWindow(int[] nums, int k) {
	int n = nums.length;
	int[] maxOfSubarrays = new int[n-k+1];
	int idx = 0;

	PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
	int start = 0; 
	int end = 0; 
	for(end = 0; end < n; end++) {
		q.add(nums[end]); 
			
		if(end-start+1 == k) {
			int max = q.peek();
			maxOfSubarrays[idx++] = max;

			if(max == nums[start]) { 
				q.remove();
			}

			start++; 
		}
	}
	return maxOfSubarrays;
}

The above code is buggy. For eg. Take nums = [9,10,9,-7,-4,-8,2,-6] and k = 5. Heap = [9,10,9,-7,-4] till i = k. When we now do peek, we get 10. i = 6, then 9 == 10, so we will just move forward and add -8. Notice, even though we have slided the window, we still have both 9 s in the heap: [9, 9, -7, -4, -8] which is not good.

Method 3 - Using MaxHeap of Pair of Value and Index ✅

In method 2, we cannot figure out the way to remove values from heap, as it takes O(k) time. What we can do is, to use a pair or [value, index] instead of just inserting the value to queue. Whenever we remove the value as max element from queue, we make sure that it is not a stale index.

Code

Java
public int[] maxSlidingWindow(int[] nums, int k) {
	int n = nums.length;
	int[] ans = new int[n-k+1];
	int idx = 0;

	// maxHeap
	PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());

	int end = 0; // window end
	for(end = 0; end < n; end++) {
	    //Pop the root (max_element),if it is out of sliding window
		while(!q.isEmpty() && (end - q.top()[1]) >= k) {
			q.pop();
		}
		
		q.add(new int[]{nums[end], end}); // add first w elements to queue
			
		if(end >= k - 1) { // We've hit the window size. Find the maximum in the current window and Slide the window ahead
			ans[idx++] = q.peek();
		}
	}
	return ans;
}

Method 4 - Using balanced BST

Algorithm

  1. Construct a self-balancing binary search tree (BST) of size w with the first w elements of the input array.
  2. Iterate through the remaining elements (n - w times):
    1. Print the maximum element from the BST.
    2. Delete the current element (arr[i]) from the BST.
    3. Insert the element k positions ahead (arr[i+k]) into the BST.

Complexity

  • ⏰ Time complexity: O(n log w)

  • 🧺 Space complexity: O(w)

  • Initializing the BST (step 1) takes O(w log w) due to insertions in a self-balancing BST.

  • Finding the maximum, deleting, and inserting elements (steps 2.1, 2.2, 2.3) each have O(log w) cost within the loop.

  • Since the loop runs n-w+1 times, the total complexity is O(w log w + (n-w+1) * log w), which simplifies to O(n log w).

Method 5 - Using DP

  • Leveraging Element Scope: We recognize that elements can contribute to windows w positions to their left and right. (This remains the same)
  • Divide and Conquer with Blocks: We exploit this by dividing the array of size n into blocks of size w, so we get n/w blocks. (This remains the same)
  • Calculating Maximums:
    • Within each block, we calculate the maximum elements seen so far (leftMax) while traversing left to right.
    • We also calculate the maximum elements remaining (rightMax) while traversing right to left.
  • Non-Overlapping Windows: Importantly, windows separated by elements less than or equal to w don’t overlap. (Change “greater than or equal to” to “less than or equal to”)
  • Resetting at Block Boundaries: We reset leftMax and rightMax values at the boundaries of each block.
  • Finding Maximum at Each Position: Finally, the maximum at each position i in the current window (slidingMax[i]) is the maximum of rightMax[i] and the corresponding leftMax[i + w - 1] shifted by w-1 positions.

This approach achieves O(n) time complexity by efficiently calculating minimum elements within and across blocks.

Dry Run

For Example: A = [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], w=4

  1. partition the array in blocks of size w=4. The last block may have less then w. 2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|

  2. Traverse the list from start to end and calculate maxSoFar. Reset min to 0 after each block (of w elements). leftMax[] = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56

  3. Similarly calculate maxInFuture by traversing from right to left. rightMax[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56

  4. now, min at each position i in current window, slidingMax[i] = min (rightMax[i], leftMax[i+w-1])

    slidingMax = 4, 6, 6, 8, 9, 10, 12, ….

Code

Java
public int[] maxSlidingWindow(int[] nums, final int k) {
  final int[] maxLeft = new int[nums.length];
  final int[] maxRight = new int[nums.length];

  maxLeft[0] = nums[0];
  maxRight[nums.length - 1] = nums[nums.length - 1];

  for (int i = 1; i < nums.length; i++) {
    maxLeft[i] = (i % k == 0) ? nums[i] : Math.min(maxLeft[i - 1], nums[i]);

    final int j = nums.length - i - 1;
    maxRight[j] = (j % k == 0) ? nums[j] : Math.min(maxRight[j + 1], nums[j]);
  }

  final int[] ans = new int[nums.length - k + 1];
  for (int i = 0, j = 0; i + k <= nums.length; i++) {
    ans[j++] = Math.min(maxRight[i], maxLeft[i + k - 1]);
  }

  return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 6 - Using Monotonic Decreasing Deque (Save Even on space) 🏆

We can use deque datastructure.

Algorithm

  • We iterate through the array, adding element indices (not values) to a deque.
  • The deque maintains only the indices of the maximum elements within the current window of size w.
  • To create the initial window, we add the first w elements and remove any smaller indices encountered, ensuring the deque holds only the maximum element indices.
  • As we slide the window by one element:
    • We remove the index falling outside the new window.
    • We again remove any smaller indices from the deque to maintain the maximum element focus.
  • The first element in the deque corresponds to the maximum element in the current window (due to the descending order based on element values).

Code

Java
public int[] maxSlidingWindow(int[] nums, int k) {
	 if (nums == null || nums.length == 0) {
		return new int[0];
	}
	int n = nums.length;
	int[] ans = new int[n - k + 1];

	// In deque we insert element at Start i.e. first
	// current max will be stored at last
	Deque<Integer> deque = new LinkedList<Integer>();
	for (int i = 0; i < n; i++) {
		// remove the item from window once index is out
		if (!deque.isEmpty() && deque.peekFirst() == i - k) {
			deque.poll();
		}

		// if Current number is already higher than numbers in deque, just remove as this can be our sliding max
		while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
			deque.removeLast();
		}

		deque.offer(i);

		// as i + 1 is more than k, we can start filling in the result
		if (i + 1 >= k) {
			ans[i + 1 - k] = nums[deque.peek()];
		}
	}

	return result;
}

Complexity

  • ⏰ Time complexity: O(n + w)
  • 🧺 Space complexity: O(w)

Dry Run

The maximum will always be the head of the queue.

int [] nums = { 11,12, 13, 12, 14, 11, 10, 9};
W = 3
Create deque for first w elements
int [] nums = { 11,12, 13, 12, 14, 11, 10, 9};
Deque:          Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
NOTE : we are adding the array index, not element
Deque: 0              Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
12>11, remove 11 from deque and add 12’s index at the end
Deque: 1              Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
13>12, remove 12 from deque and add 13’s index at the end
Deque: 2              Output: 13  (First index in deque)
At this point our first window with w elements is prepared. Now we will start discarding the elements from the deque which falls outside the window.
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 1-3 so remove indexes less than 1 from deque if present.
2. 12<13, add 12’s index at the end 
Deque: 2 3              Output: 13 13
 __________________________________ 
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 
1. Indexes for new window 2-4 so remove indexes less than 2 from deque if present. 
2. 14>12, remove 12 and 14>13, remove 13. Add 14 at the end
Deque: 4              Output: 13 13 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 3-5 so remove indexes less than 3 from deque if present.
2. 11< 14, Add 11 at the end
Deque: 4 5            Output: 13 13 14 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 4-6 so remove indexes less than 4 from deque if present.
2. 10< 11, Add 10 at the end
Deque: 4 5 6          Output: 13 13 14 14 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 4-7 so remove indexes less than 4 from deque if present. So 4 will be removed from deque.
2. Deque: 5 6
3. 9< 10, Add 9 at the end
Deque: 5 6 7          Output: 13 13 14 14 14 11
__________________________________