Sliding Window Maximum hard

Problem Statement

Given an array nums and an integer k, return the maximum value in each subarray of size k. Use a deque to efficiently manage the sliding window.

Example 1:

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

Example 2:

Input: nums = [1], k = 1 Output: [1]

Steps:

1. Initialization: Create a deque dq to store indices of elements. This deque will maintain the indices of elements that are potential maximums in the current window.

2. Sliding Window: Iterate through the input array nums.

   • Removal of outdated elements: If the front element of the deque is outside the current window (its index is smaller than i - k + 1), remove it from the front.
   • Removal of smaller elements: While the deque is not empty and the element at the back of the deque is smaller than the current element, remove the element from the back. This ensures that the deque only contains indices of elements that are potentially maximums.
   • Add current element: Add the current element's index to the back of the deque.

3. Result: Once the window is of size k, the front element of the deque will always represent the maximum in the current window. Add this maximum to the result vector.

Explanation:

The deque dq acts as a monotonic decreasing queue. It stores indices, not values. This is crucial for efficiency. By maintaining a decreasing order, we ensure that the maximum element is always at the front. When we slide the window, we remove elements that are no longer within the window and elements that are guaranteed to be smaller than future elements (hence, not potential maximums). This allows us to find the maximum in O(1) time for each window.

Code:

#include <vector>
#include <deque>

using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq;

    for (int i = 0; i < nums.size(); ++i) {
        // Remove outdated elements from the front
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // Remove smaller elements from the back
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // Add current element's index to the back
        dq.push_back(i);

        // Add maximum to result if window size is k
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

Complexity:

• Time Complexity: O(N), where N is the length of the input array. Each element is added and removed from the deque at most once.
• Space Complexity: O(k), because the deque can hold at most k elements. In the worst case, the deque will hold all indices within the window.