Sliding Window Maximum – 239. LeetCode

The “Sliding Window Maximum” problem involves finding the maximum value in a sliding window of a fixed size as it moves across an array. Think of it as looking through a fixed-size frame at a sequence of numbers and finding the biggest number within the frame as you slide it from the start to the end of the sequence.

Brute-Force Approach

public List<Integer> maxSlidingWindow(int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i <= nums.length - k; i++) {
        int max = Integer.MIN_VALUE;
        for (int j = i; j < i + k; j++) {
            max = Math.max(max, nums[j]);
        }
        result.add(max);
    }
    return result;
}

This brute-force approach iterates over all possible windows of size k in the array. For each window, we find the maximum value by scanning all elements in the window. The result list stores these maximum values.

• Outer Loop: Moves the sliding window across the array.

• Inner Loop: Scans the current window to find the maximum value.

Optimal Algorithm: Deque (Double-Ended Queue)

The Deque data structure supports efficient insertion and deletion from both ends, making it ideal for maintaining the indices of potential maximum values in the current window.

• Pattern: Sliding Window Optimization

• This pattern involves maintaining a data structure that represents the current state of the window, updating it as the window slides.

• When to Use:

• Problems requiring maximum, minimum, or other aggregates over a sliding window.

• The problem characteristics include a moving fixed-size range (window) over a data structure like an array.

Deque efficiently removes indices that are out of range or no longer relevant (smaller than the current element). This makes it ideal for sliding window problems, providing linear time complexity.

Steps of Algorithm

1. Initialize an empty deque to store indices.

2. Slide the window across the array:

• Remove indices outside the current window.

• Remove indices of elements smaller than the current element.

• Add the current index to the deque.

• Add the maximum element (at deque front) to the result list after the first window.

public List<Integer> maxSlidingWindow(int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside the current window
        if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove indices of elements smaller than the current element
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        // Add the current index
        deque.offerLast(i);
        // Add the max element to the result after the first window
        if (i >= k - 1) {
            result.add(nums[deque.peekFirst()]);
        }
    }
    return result;
}

Line-by-Line Explanation

List<Integer> result = new ArrayList<>();

• Creates a list to store the maximum values for each sliding window.
• The final output of the function is a list of the maximum values, so we need a structure to store them.

Deque<Integer> deque = new ArrayDeque<>();

• Creates a deque (double-ended queue) to keep track of the indices of the array elements.
• The deque helps efficiently track the indices of elements that are candidates for being the maximum in the current window.

for (int i = 0; i < nums.length; i++) {

• Loop through all the elements in the array
• To process each element in the array as part of a sliding window.

if (!deque.isEmpty() && deque.peekFirst() < i - k + 1)

• Check if the element at the front of the deque is outside the current sliding window.
• If an element’s index is no longer within the current window range, it is removed because it can no longer contribute to the maximum of the window.

deque.pollFirst();

• Removes the index from the front of the deque.
• Ensure that the deque only contains indices of elements within the current window.

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])

• Removes indices of elements from the back of the deque that are smaller than the current element.
• Smaller elements cannot be the maximum of the current or any future windows. Removing them keeps the deque focused only on relevant indices.

deque.pollLast();

• Removes the last index from the deque.
• Eliminates elements that are no longer candidates for the maximum, ensuring the deque remains efficient.

if (i >= k - 1)

• Checks if the sliding window has reached its full size.
• We only start recording maximums in the result list once the window size is k.

result.add(nums[deque.peekFirst()]);

• Adds the maximum value of the current window (found at the front of the deque) to the result list.
• The front of the deque always contains the index of the maximum element in the current window.

Summary Of Key Points

• The deque contains only indices of elements that are relevant for the current window.

• Indices of smaller elements are removed to ensure the deque is efficient.

• Maximum values are calculated once the window is fully formed.

• The approach avoids unnecessary work by focusing only on the most relevant candidates for the maximum.