hard Sliding Window Maximum

Problem Statement

You are given an array of integers nums, and integer k, size of the sliding window which moves from the very left to the very right in the array. In each window, you can have only k numbers, and the window moves one position right by each time.

Return the array containing the maximum element of each sliding window.

Examples

Example 1:

• Input: nums = [2, 1, 5, 1, 3, 2], k = 3
• Expected Output: [5, 5, 5, 3]
• Justification: Here, the window of size 3 moves across the array. The maximum values in each window are 5 (from [2, 1, 5]), 5 (from [1, 5, 1]), 5 (from [5, 1, 3]), and 3 (from [1, 3, 2]).

Example 2:

• Input: nums = [4, -2, -3, 4, 1], k = 2
• Expected Output: [4, -2, 4, 4]
• Justification: The maximum values in each window of size 2 are 4 (from [4, -2]), -2 (from [-2, -3]), 4 (from [-3, 4]), and 4 (from [4, 1]).

Example 3:

• Input: nums = [9, 7, 2, 4, 6], k = 4
• Expected Output: [9, 7]
• Justification: In this case, there are only two windows of size 4. The maximum value in the first window is 9 (from [9, 7, 2, 4]), and in the second window is 7 (from [7, 2, 4, 6]).

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

Solution

To solve this problem, we'll use a deque (double-ended queue) to maintain the indices of the elements in the current window, ensuring the deque always has the maximum element's index at the front. This approach works because it allows us to efficiently remove elements that are no longer in the window (by checking if they are out of the current window's range) and ensure the first element in the deque is always the maximum of the current window. We'll iterate through the array, adding each element's index to the deque while maintaining these properties.

This method is effective because it combines the efficiency of a queue for managing the window's sliding mechanism with the ability to quickly update and retrieve the maximum value. By only storing relevant indices and removing those that are no longer in the window or are not potential maximums, we significantly reduce the time complexity compared to brute force methods that check every window's maximum separately.

Step-by-step Algorithm

• Initialize an empty deque D to store indices of array elements.
• Iterate through each element of the array nums:
  • If D is not empty and the front element of D is out of the current window's range (i - k), pop it from the front.
  • While D is not empty and the current element is greater than the element at the back of D, pop elements from the back. This ensures that the first element in D is always the maximum of the current window.
  • Add the current index i to the back of D.
  • If i is greater than or equal to k - 1, append the front element of D to the result array, as the window has now reached its full size.
• Return the result array containing the maximums.

Algorithm Walkthrough

Let's consider the input: nums = [2, 1, 5, 1, 3, 2], k = 3

1. Initialization:

   • The deque D is initialized as empty.
   • An empty result array is initialized to store the maximum of each window.

2. Iteration 1 (i = 0, nums[i] = 2):

   • Since D is empty, add index 0 to D.
   • D now contains [0].
   • The window has not yet reached its full size (k = 3), so we don't add anything to the result array.

3. Iteration 2 (i = 1, nums[i] = 1):

   • No indices are removed from D since all indices in D are within the current window's range.
   • nums[i] is less than nums[D.back()] (1 < 2), so just add index 1 to D.
   • D now contains [0, 1].
   • The window has not reached its full size, so no action on the result array.

4. Iteration 3 (i = 2, nums[i] = 5):

   • No indices are removed from D for being out of range.
   • nums[i] is greater than nums[D.back()], so remove indices from D while nums[i] is greater than nums[D.back()]. Remove 0 and 1 from D.
   • Add index 2 to D since nums[2] is now the greatest so far.
   • D now contains [2].
   • The window has reached its full size. Add nums[D.front()] (which is 5) to the result array.

5. Iteration 4 (i = 3, nums[i] = 1):

   • No indices are removed from D for being out of range.
   • nums[i] is less than nums[D.back()], so just add index 3 to D.
   • D now contains [2, 3].
   • Add nums[D.front()] (which is still 5) to the result array since the window is full.

6. Iteration 5 (i = 4, nums[i] = 3):

   • No indices are removed from D for being out of range.
   • nums[i] is greater than nums[D.back()] (the index at D.back() is 3, and nums[3] is 1), so remove index 3 from D.
   • Add index 4 to D.
   • D now contains [2, 4].
   • Add nums[D.front()] (which is 5) to the result array.

7. Iteration 6 (i = 5, nums[i] = 2):

   • Remove index 2 from D since it's out of the current window's range (i - k + 1 = 3).
   • nums[i] is less than nums[D.back()], so just add index 5 to D.
   • D now contains [4, 5].
   • Add nums[D.front()] (which is 3) to the result array.

8. Final Result:

   • The result array, which contains the maximum of each window, is [5, 5, 5, 3].

Code

import java.util.*;

public class Solution {

  public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) {
      return new int[0];
    }
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>();

    for (int i = 0; i < n; i++) {
      // Remove numbers out of range k
      while (!deque.isEmpty() && deque.peek() < i - k + 1) {
        deque.poll();
      }
      // Remove smaller numbers in k range as they are useless
      while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
        deque.pollLast();
      }
      // Add new value
      deque.offer(i);
      if (i >= k - 1) {
        result[i - k + 1] = nums[deque.peek()];
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    int[] nums1 = { 2, 1, 5, 1, 3, 2 };
    int k1 = 3;
    System.out.println(Arrays.toString(solution.maxSlidingWindow(nums1, k1)));
    // Example 2
    int[] nums2 = { 4, -2, -3, 4, 1 };
    int k2 = 2;
    System.out.println(Arrays.toString(solution.maxSlidingWindow(nums2, k2)));
    // Example 3
    int[] nums3 = { 9, 7, 2, 4, 6 };
    int k3 = 4;
    System.out.println(Arrays.toString(solution.maxSlidingWindow(nums3, k3)));
  }
}

Complexity Analysis

Time Complexity

• : Each element in the array is processed exactly twice - once when it's added to the deque and once when it's removed. This leads to a linear time complexity because the operations of adding to and removing from the deque (or its equivalent data structure) are O(1) operations.

Space Complexity

• : In the worst-case scenario, the space complexity is due to the storage requirements of the result array, which contains at most N - k + 1 elements. The deque (or similar structure) itself will have at most k elements because it only stores elements from the current window. However, since k is a constant that does not scale with the input size N, the dominant term for space complexity is due to the output array, making it .

🎯 STRICT STANDOUT — Solution Sliding Window Maximum

0. Pattern family

Family: Monotonic decreasing deque of indices

1. Why / judgment (K3)

Need max of every window of size k in O(n). Deque stores candidates in decreasing value order; front is current max. Pop back while smaller/equal than incoming (they can never be max while new one exists); pop front when out of window. Judgment: heap is O(n log n) with lazy deletes; deque is amortized O(1)/element. Multiset also O(n log k).

2. Worked complexity / derivation (K11)

Each index pushed once, popped once → O(n) time, O(k) deque space.
Output size n−k+1. Heap: O(n log n). Sparse table RMQ: O(n log n) prep + O(1) — overkill if one-shot.

3. Pattern + recognition + when-NOT (K12)

Name: MONOQUEUE — SLIDING WINDOW MAXIMUM

Recognition: fixed window k; stream maxima; online array pass.

When-NOT: If window minimum → increasing deque. If sum/avg → prefix or sliding sum, not monoqueue. If dynamic k → different.

4. Edge hand-run (K13)

nums=[1,3,-1,-3,5,3,6,7] k=3 → [3,3,5,5,6,7]
Hand: after i=2 deque idx of 3,-1 → max3; … final 7.
Edge: k=1 → copy array. k=n → single global max. negatives OK.

5. Interviewer follow-ups & drills

Q1. Why store indices not values?
Model answer: Need to know when front leaves the window.

Q2. Why pop equal from back?
Model answer: Later equal is more useful (stays longer); optional but keeps deque lean.

Q3. Amortized proof?
Model answer: Each index ≤1 push and ≤1 pop.