Sliding Window maximum

Problem Overview

LeetCode Question: Sliding Window Maximum
Topic: Stack and Queue
Difficulty: Hard

The problem is about finding the maximum value in a sliding window that moves from the beginning to the end of a list (array). Given an array of integers and a window size k, the task is to create an output list containing the maximum value of each window as the window progresses.

Understanding the Problem

Consider an array nums and a positive integer k. You need to slide a window of size k across nums and output the maximum element in every window. The window moves right by one element each time.

For example, given nums = [1,3,-1,-3,5,3,6,7] and k = 3, the output should be [3,3,5,5,6,7]. Here's the trailing part of the process:

• Window position 0-2 (elements: [1,3,-1]) ⇒ Maximum = 3
• Window position 1-3 (elements: [3,-1,-3]) ⇒ Maximum = 3
• Window position 2-4 (elements: [-1,-3,5]) ⇒ Maximum = 5
• and so forth.

Key DSA Concepts and Theory

To solve this problem efficiently, understanding the following data structures and techniques is essential:

Deque (Double Ended Queue)

A deque is an advanced version of the queue data structure which allows insertion and deletion of elements from both ends (front and back). The double-ended nature of the deque is particularly useful in maintaining the potential maximum elements of the current window efficiently.

Sliding Window Technique

This technique involves maintaining a subset (window) of elements from an array. The window slides sequentially from the start of the array to the end. During each slide, some operation is efficiently performed over the elements within the current window.

Monotonic Queue

A monotonic queue is a type of queue that maintains its elements in a sorted order. For our problem, we can utilize a queue that remains in decreasing order to quickly fetch the maximum element from the current window.

Solution Approach

We use a deque to maintain the indices of array elements. This deque will store elements in a decreasing order, making it easy to retrieve the maximum element in constant time O(1). Here’s the step-by-step process:

1. Initialize an empty deque dq to store indices, and a list result to store the maximum values.

2. Iterate over each element in the array using its index i:

   • Remove indices from the front of the dq that are out of the bounds of the current window.
   • Remove indices from the back of the deque if the corresponding values in nums are less than or equal to the current value.
   • Add the current index i to the dq.
   • If i is greater than or equal to k-1, append the value nums[dq.front()] to result as it represents the maximum for the current window.

3. Finally, return the result.

C++ Implementation

#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::deque<int> dq;
    std::vector<int> result;
    
    for (int i = 0; i < nums.size(); ++i) {
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

Java Implementation

import java.util.*;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            if (!dq.isEmpty() && dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        
        return result;
    }
}

Time and Space Complexity Analysis

Time Complexity

The time complexity is O(n), where n is the number of elements in the array. Each element is added and removed from the deque at most once, leading to linear time complexity.

Space Complexity

The space complexity is O(k). The deque stores up to k indices, corresponding to the window size.

Common Mistakes to Avoid

1. Ignoring Edge Cases:

   • Ensure that the window does not slip past the bounds of the array.
   • Handle cases where k equals 1, returning the array as is.

2. Incorrect Index Maintenance:

   • Ensure the indices stored in the deque are coherent with the sliding window range.

Similar Problems on LeetCode

1. Problem 239: Sliding Window Maximum
2. Problem 862: Shortest Subarray with Sum at Least K
3. Problem 862: Sliding Window Median

Additional Resources and References

1. Deque Data Structure on GeeksforGeeks
2. Sliding Window Technique Explained
3. Monotonic Queue Explained

Understanding these concepts and applying them to the sliding window problem will not only solve this specific problem but also enhance your approach to solving a variety of related problems efficiently.