Leetcode 239: Sliding Window Maximum

The Sliding Window Maximum is a common algorithm problem where, given an array of integers and a window size k, you are asked to find the maximum number in each sliding window of size k as the window moves from left to right across the array.

Problem Description for 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: 
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]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

Solution(s);

1. Brute Force Approach:

The simplest solution is to iterate over each window and find the maximum of the k elements manually. This approach is intuitive but highly inefficient for larger arrays, as it recalculates the maximum every time the window slides.

Code:

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        
        return result;
    }
}

Explanation:

• We loop through each possible window, and for each window, we calculate the maximum by checking all k elements in that window.
• Time complexity: O(n * k), where n is the length of the array and k is the window size.

This approach works for small inputs but will time out for larger inputs due to its inefficiency.

2. Optimized Approach using Deque:

To improve the solution, we can use a deque (double-ended queue) to maintain a decreasing sequence of indices of elements in the current window. The front of the deque will always hold the index of the maximum element in the current window.

Key Idea:

(a).The deque will hold indices, not values.

(b).For each element in nums, we:

• Remove elements from the deque if they are outside the bounds of the current window.
• Remove elements smaller than the current element from the deque, as they will never be the maximum in this or any future window.
• Append the current element index to the deque.
• If the window has reached its full size, add the value at the front of the deque (the maximum of the current window) to the result.

Code:

import java.util.*;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Remove elements that are out of this window
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove elements that are smaller than the current element
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add current element index at the end
            deque.offerLast(i);

            // The element at the front is the largest in the window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

Explanation:

1.Deque Operations:

• Adding Elements: We add the current index to the deque while maintaining a decreasing order.
• Removing Elements: We remove elements that are out of the current window or smaller than the current element because they are no longer useful.

2.Time Complexity:

• Each element is added and removed from the deque at most once. Hence, the overall time complexity is O(n), where n is the number of elements in nums.

3.Space Complexity: O(k) due to the deque storing at most k elements at any time.

This solution is highly efficient for large inputs and leverages the deque to maintain a sliding window of potential candidates for the maximum value.

3. Using Priority Queue (Max-Heap):

Another approach is to use a max-heap (priority queue) to store the elements of the current window. The root of the max-heap always holds the maximum element of the current window.

Code:

import java.util.*;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        
        for (int i = 0; i < n; i++) {
            // Add the current element to the heap (as a pair of value and index)
            maxHeap.offer(new int[]{nums[i], i});
            
            // Remove elements not within the window (i.e., with index out of bounds)
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            
            // The root of the heap is the max of the current window
            if (i >= k - 1) {
                result[i - k + 1] = maxHeap.peek()[0];
            }
        }
        
        return result;
    }
}

Explanation:

• We push each element into the max-heap as a pair [value, index].
• After adding each element, we ensure that the top of the heap is the maximum of the current window by removing any element whose index is outside the window.
• The max-heap allows us to efficiently keep track of the maximum in each window.
• Time Complexity: O(n log k) due to heap operations.
• Space Complexity: O(k) because of the heap storing up to k elements at any time.

Conclusion:

For solving sliding window maximum, the Deque Approach offers the best time complexity of O(n) and works efficiently for large inputs. The brute force approach provides clarity on the problem but isn’t feasible for large inputs due to its O(n*k) complexity. The Max-Heap Approach is also a valid alternative but has higher time complexity (O(n log k)) than the deque-based solution.

For most real-world scenarios involving sliding windows, the deque-based solution is preferred due to its optimal performance.

FAQs for Leetcode 239: Sliding Window Maximum:

Q1: What is the Sliding Window Maximum problem?

A1: The Sliding Window Maximum problem involves finding the maximum element in every subarray (or window) of size k as it slides from the beginning to the end of a given array. At each new position of the window, we output the maximum value of the current window.

Q2: What are the common approaches to solve the Sliding Window Maximum problem?

A2: There are three primary approaches to solve this problem:

• Brute Force Approach (O(n * k)): Iterate through each window, and compute the maximum value by scanning all elements inside the window.
• Deque Approach (O(n)): Use a double-ended queue to maintain the indices of elements in decreasing order of their values, ensuring the maximum is at the front of the deque.
• Priority Queue/Max-Heap Approach (O(n log k)): Use a max-heap to keep track of the largest elements in the window.

Q3: Why is the deque (double-ended queue) approach optimal for this problem?

A3: The deque approach is optimal because it allows us to efficiently track the maximum in each sliding window while only processing each element at most twice (once when adding it to the deque and once when removing it). This results in a time complexity of O(n), which is better than other approaches that require recalculating or reorganizing elements for each window.

Q4: How does the deque approach work?

A4: The deque stores the indices of the array elements in decreasing order of their values:

• As we slide the window, we remove elements from the front of the deque that fall outside the current window.
• We also remove elements from the back that are smaller than the current element, as they will no longer contribute to the maximum of future windows.
• The element at the front of the deque is always the largest element in the current window.

Q5: How do you handle edge cases in the Sliding Window Maximum problem?

A5: Key edge cases to handle include:

• Small arrays where nums.length is smaller than k.
• All negative numbers, where the maximum will still be the least negative number.
• Window size k = 1, where the result will be the same as the input array since each window contains only one element.
• Window size equal to the array length, where the output will be the maximum of the entire array.