Sliding Window Maximum Using Priority Queue

Introduction

The Sliding Window Maximum problem is a classic algorithmic challenge that arises in various scenarios, especially in data analysis and streaming applications. The problem can be stated as follows:

Given an array of integers and a number k, find the maximum for each sliding window of size k across the array.

For example, if you have the array [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the sliding windows would be:

• Window 1: [1, 3, -1] → Maximum = 3
• Window 2: [3, -1, -3] → Maximum = 3
• Window 3: [-1, -3, 5] → Maximum = 5
• Window 4: [-3, 5, 3] → Maximum = 5
• Window 5: [5, 3, 6] → Maximum = 6
• Window 6: [3, 6, 7] → Maximum = 7

The expected output for the above example would be [3, 3, 5, 5, 6, 7].

Why Use a Priority Queue?

A naive approach would involve iterating through each window and determining the maximum for each, which takes O(k) time for every window in a total of O(n*k) time complexity where n is the number of elements in the array. This is not efficient, especially for larger inputs.

Instead, we can utilize a priority queue (or max-heap) to achieve much greater performance. A priority queue allows us to efficiently insert, delete, and extract maximum (or minimum) elements, leading to an overall time complexity of O(n log k) for this problem.

Implementation in Java

Let's get into the implementation details. Below is a Java code snippet demonstrating how to solve the Sliding Window Maximum problem using a priority queue:

import java.util.*;

public class SlidingWindowMaximum {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 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]); // Max-Heap for maximum retrieval

        for (int i = 0; i < n; i++) {
            maxHeap.offer(new int[]{nums[i], i}); // Store both value and its index

            // Remove elements out of the current window
            if (i >= k - 1) {
                while (maxHeap.peek()[1] < i - k + 1) {
                    maxHeap.poll(); // Remove old entries
                }
                result[i - k + 1] = maxHeap.peek()[0]; // The current maximum is at the top
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
    
        System.out.println("Sliding Window Maximum: " + Arrays.toString(result));
    }
}

Explanation of the Code

1. Input and Initialization: The method maxSlidingWindow takes an integer array nums and an integer k. We initialize a result array of the size n - k + 1 to store maximum values and a priority queue to maintain the current window's maximum values.

2. Iterating Over the Input Array:

   • For each element in the array, we add it along with its index to the priority queue.
   • After processing the first k elements, we begin to store results.

3. Maintenance of the Sliding Window:

   • Before recording the current maximum, we ensure that we remove any elements from the top of the priority queue that are no longer in the current sliding window. This is achieved by checking if the index of the element at the top of the heap is less than the current window's starting index (i - k + 1).

4. Storing the Maximum: The element at the top of the priority queue (maxHeap.peek()[0]) holds the maximum value of the current sliding window, which we store in the results array.

5. Output: Finally, the resulting array of sliding window maximums is printed in the main method.

Conclusion

This approach harnesses the power of priority queues to efficiently compute the maximum values within sliding windows in an array. Using a max-heap allows us to maintain a running maximum in logarithmic time, making it a chic solution for handling this type of problem efficiently.

Feel free to experiment with different inputs and see how the algorithm performs! Happy coding!