DAY 74 - 239. Sliding Window Maximum

Hey Guys! Today we are on the 74th day and we are going to solve today's daily leetcode problem. Let's start with breaking down the problem and then get to into the algorithm.

Question: 239. Sliding Window Maximum

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.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:

Question Breakdown:

• The question is pretty simple. Imagine a I give you a window of size K(basically you can only look at 3 elements max at once), you have to return the maximum value that exists in that window.
• Now We just have to shift that window till we reach the end of array.
• Let's try this approach and see what happens:

Brute Force Approach:

The first approach involves using a brute force method combined with searching for the maximum element within the current window. In this algorithm we maintain a sliding window of size k as given and iterate through the array. In each iteration, we search for the maximum element within the window and append it to our answer.

This code will give you a TLE(Time Limit Exceeded) because it's highly time inefficient.

Code:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    // Initialize result vector
    vector<int> res;
    int n = nums.size();

    // Iterate through the array
    for (int left = 0; left <= n - k; left++) {
        // Find the maximum element within the window
        int maxi = *max_element(nums.begin() + left, nums.begin() + left + k);
        res.push_back(maxi);
    }   

    return res;
}

Optimal Approach Using Deque:

In the second approach we utilize a deque (double-ended queue) to efficiently keep track of the maximum element within the sliding window.
In this algorithm we maintain a deque containing potential candidates for the maximum element. It iterates through the array and updates the deque to always have the maximum element at the front.

Code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // Initialize result vector
        vector<int> res;
        int n = nums.size();
        deque<int> dq;

        // Iterate through the array
        for (int right = 0; right < n; right++) {
            // Remove elements from the back of the deque that are smaller than the current element
            while (!dq.empty() && dq.back() < nums[right]) {
                dq.pop_back();
            }
            dq.push_back(nums[right]);

            // Check if the window size is reached
            if (right - left + 1 >= k) {
                res.push_back(dq.front());
                // Remove the leftmost element if it's the maximum element
                if (dq.front() == nums[left]) {
                    dq.pop_front();
                }
                left++;
            }
        } 

        return res;
    }
};

Complexity Analysis: