The Question

Sliding Window Maximum

You are given an array of integers nums and 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 which contains the maximum value for each window position. Example: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Constraints: - 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 - 1 <= k <= nums.length

Java

Monotonic Deque

Sliding Window

Questions & Insights

Clarifying Questions

What are the constraints on the size of the input array

n

and the window size

k

? (Assumed

1 \le k \le n \le 10^5

Can the array contain negative integers? (Assumed yes, any standard integer value).

How should the function behave if

k=1

k=n

? (Assumed standard behavior: if

k=1

, return the array itself; if

k=n

, return an array with a single element containing the global maximum).

Is the input array guaranteed to be non-null? (Assumed non-null and non-empty).

Assumptions:

Time complexity must be better than

O(n \cdot k)

(ideally

O(n)

) to handle large inputs.

The output should be an integer array of size

n - k + 1

Thinking Process

A naive solution would involve scanning the window for every slide, leading to

O(n \cdot k)

. To optimize, we need a way to track the maximum value efficiently as we add one element and remove another.

We can use a Monotonic Deque (double-ended queue) to store indices of elements. We maintain the deque such that the values corresponding to the indices are always in strictly decreasing order.

For every index

i

n the array:

Clean up front: Remove indices from the front of the deque if they are outside the current window (i.e., index <= i - k).

Maintain monotonicity: Before adding the current index

i

, remove all indices from the back of the deque whose values are less than or equal to nums[i]. These elements can never be the maximum for any future window.

Add current: Push the current index

i

onto the back of the deque.

Record result: If

i \ge k - 1

(the window is full), the element at the front of the deque is the maximum for the current window.

Implementation Breakdown

Problem Set

Functional Requirement: Given an array nums and an integer k, return an array representing the maximum value in each sliding window of size k.

Constraints:

1 \le nums.length \le 10^5

-10^4 \le nums[i] \le 10^4

1 \le k \le nums.length

Approach

Algorithm: Monotonic Deque

Data Structure: java.util.ArrayDeque

Complexity:

Time:

O(n)

because each element is pushed and popped from the deque at most once.

Space:

O(k)

for the deque storing indices within the current window.

Implementation

Wrap Up

Advanced Topics

Performance Optimization: In highly performance-critical systems, java.util.ArrayDeque (which stores Integer objects) can lead to boxing/unboxing overhead. A custom primitive-based deque using a fixed-size array can further reduce latency and GC pressure.

Two-Pass Approach: Alternatively, one could use a prefix/suffix maximum approach. By dividing the array into blocks of size

k

and calculating max from left and right within blocks, we can find the window max in

O(n)

time without a deque. This is often more cache-friendly.

Parallelization: For massive datasets, we can split the array into chunks. Overlapping windows at chunk boundaries must be handled by sharing the prefix/suffix maximums of the boundary regions between processors.