Leetcode 239 - Sliding Window Maximum

Link : https://leetcode.com/problems/sliding-window-maximum/

import java.util.*;

/**
 * LeetCode 239: Sliding Window Maximum
 * 
 * Problem: Given an array nums and a sliding window of size k moving from the leftmost
 * to the rightmost, return the maximum element in each window.
 * 
 * Key Implementation Details:
 * 1. Non-destructive operations
 * 2. Space-time trade-offs
 * 3. Input validation
 * 4. Efficient data structures (Deque)
 * 
 * Example:
 * 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
 */
public class SlidingWindowMaximum {

    /**
     * Finds maximum in each sliding window using Deque.
     * 
     * Time Complexity: O(n) - each element is processed at most twice
     * Space Complexity: O(k) - deque stores at most k elements
     * 
     * @param nums Input array
     * @param k Window size
     * @return Array of maximum values for each window
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        // For single element window, return array as is
        if (k == 1) {
            return nums.clone();
        }

        // Result array to store maximums
        int[] result = new int[nums.length - k + 1];
        int resultIndex = 0;

        // Deque to store indices of potential maximum values
        Deque<Integer> deque = new ArrayDeque<>();

        // Process first k elements
        for (int i = 0; i < k; i++) {
            // Remove smaller elements from back
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        // Add maximum of first window
        result[resultIndex++] = nums[deque.peekFirst()];

        // Process rest of the array
        for (int i = k; i < nums.length; i++) {
            // Remove elements outside current window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements from back
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.offerLast(i);
            result[resultIndex++] = nums[deque.peekFirst()];
        }

        return result;
    }

    /**
     * Brute force solution for comparison.
     * Time Complexity: O(nk)
     * Space Complexity: O(1)
     */
    public int[] maxSlidingWindowBrute(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        if (k == 1) {
            return nums.clone();
        }

        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i <= nums.length - k; i++) {
            int max = nums[i];
            for (int j = 1; j < k; j++) {
                max = Math.max(max, nums[i + j]);
            }
            result[i] = max;
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();

        // Test cases
        TestCase[] testCases = {
            new TestCase(
                new int[]{1, 3, -1, -3, 5, 3, 6, 7},
                3,
                "Standard case from problem description"
            ),
            new TestCase(
                new int[]{1},
                1,
                "Single element"
            ),
            new TestCase(
                new int[]{1, -1},
                1,
                "Window size 1"
            ),
            new TestCase(
                new int[]{1, 2, 3, 4, 5},
                5,
                "Window size equals array length"
            ),
            new TestCase(
                new int[]{1, 1, 1, 1, 1},
                2,
                "All same elements"
            ),
            new TestCase(
                new int[]{5, 4, 3, 2, 1},
                3,
                "Decreasing sequence"
            ),
            new TestCase(
                new int[]{1, 2, 3, 4, 5},
                3,
                "Increasing sequence"
            ),
            new TestCase(
                new int[]{-7, -8, 7, 5, 7, 1, 6, 0},
                4,
                "Mixed positive and negative"
            ),
            new TestCase(
                new int[]{1, -9, 8, -6, 5, -3, 2, -1},
                3,
                "Alternating positive and negative"
            ),
            new TestCase(
                new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 1, 2, 3},
                2,
                "Extreme values"
            )
        };

        for (TestCase test : testCases) {
            runTest(solution, test);
        }
    }

    private static class TestCase {
        int[] nums;
        int k;
        String description;

        TestCase(int[] nums, int k, String description) {
            this.nums = nums;
            this.k = k;
            this.description = description;
        }
    }

    private static void runTest(SlidingWindowMaximum solution, TestCase test) {
        System.out.println("\nTest: " + test.description);
        System.out.println("Input array: " + Arrays.toString(test.nums));
        System.out.println("Window size: " + test.k);

        // Test optimized solution
        int[] optimizedResult = solution.maxSlidingWindow(test.nums, test.k);
        System.out.println("Optimized solution: " + Arrays.toString(optimizedResult));

        // Test brute force solution
        int[] bruteResult = solution.maxSlidingWindowBrute(test.nums, test.k);
        System.out.println("Brute force solution: " + Arrays.toString(bruteResult));

        // Verify solutions match
        boolean match = Arrays.equals(optimizedResult, bruteResult);
        System.out.println("Solutions match: " + match);

        // Verify correctness of result
        boolean correct = verifyResult(test.nums, test.k, optimizedResult);
        System.out.println("Result verified: " + correct);
    }

    /**
     * Helper method to verify the result is correct
     */
    private static boolean verifyResult(int[] nums, int k, int[] result) {
        if (nums == null || nums.length == 0) {
            return result.length == 0;
        }

        if (k == 1) {
            return Arrays.equals(nums, result);
        }

        if (result.length != nums.length - k + 1) {
            return false;
        }

        // Check each window
        for (int i = 0; i < result.length; i++) {
            int windowMax = nums[i];
            for (int j = 0; j < k; j++) {
                windowMax = Math.max(windowMax, nums[i + j]);
            }
            if (windowMax != result[i]) {
                return false;
            }
        }

        return true;
    }
}