Sliding Window Maximum problem and solution in Java and Python

“Sliding Window Maximum” is a classic FAANG problem involving arrays and dequeues. The goal is to find the maximum in every window of size k as it slides through an array.

Problem Statement

• Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
• Output: [3,3,5,5,6,7]
• Explanation: Maximums in each sliding window:

[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️⃣ Python Solution – Using Deque (O(n))

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices
    result = []

    for i, num in enumerate(nums):
        # Remove indices outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements from the end
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # Append current max to result
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(maxSlidingWindow(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

✅ Key idea: Keep indices of elements in decreasing order in deque. Front always has max of current window.

2️⃣ Java Solution – Using Deque (O(n))

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new LinkedList<>();
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0;

        for (int i = 0; i < n; i++) {
            // Remove indices outside the window
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }

            // Remove smaller elements from the end
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }

            dq.offerLast(i);

            // Append current max to result
            if (i >= k - 1) {
                result[ri++] = nums[dq.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k))); // [3, 3, 5, 5, 6, 7]
    }
}

⚡ Key Points for FAANG

1. Deque stores indices, not values.

2. Maintain decreasing order in deque: front = max of current window.

3. Remove elements:

   • Outside the window
   • Smaller than the current number

4. Time Complexity: O(n)

5. Space Complexity: O(k)

✅ Alternative: Use a max-heap, but time complexity is O(n log k), which is slower.