Deque Based Sliding Window Maximum in Java

Image Source

Sliding window maximum comes up a lot in coding interviews and data processing work where you need the largest value in every window of size k across an array. Directly recomputing the maximum from scratch for every window tends to run too slowly on large inputs. With a deque based method, the code keeps only the indexes that still have a chance to be the maximum and drops stale indexes as the window moves, which keeps the running time linear in the length of the array.

Deque Based Sliding Window Maximum in Java

With a deque based method, the whole process turns into a single pass where the index moves from left to right and a small structure tracks which positions are still worth keeping. As the index i advances, entries at the front of the deque that fall to the left of the current window bounds are removed, and entries at the back whose values are smaller than nums[i] are dropped because they can never become the maximum for any later window that includes i. The front of the deque always holds the index of the current maximum for the active window, so after the window reaches size k, the maximum for that window is just nums[deque.peekFirst()].

Sliding Window Maximum Problem Basics

Sliding window maximum refers to a situation where you have an integer array nums of length n and a window size k, and the goal is to report the largest value inside every contiguous block of k elements. The window starts at the front of the array, covers the first k positions, then moves one index to the right at a time until the right edge reaches the end. The general requirement is that 1 <= k <= n, so every window has at least one element and never runs off the edge.

Take this common example with nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The first window covers indexes 0, 1, 2, which gives values [1, 3, -1] and a maximum of 3. After the window moves one step, it covers indexes 1, 2, 3, which gives [3, -1, -3] and still has a maximum of 3. That motion keeps going until the last window covers indexes 5, 6, 7 with values [3, 6, 7] and a maximum of 7. The result array that collects all those maximums is [3, 3, 5, 5, 6, 7].

The count of windows is always n - k + 1. That value comes from looking at the starting index of the window. The earliest starting index is 0 and the latest starting index is n - k, so there are n - k + 1 different starting positions in that range. This small detail matters later when you size the result array and when you build loops that fill it.

Take this helper method that prints each window’s index range:

Running this helper makes the sliding motion more concrete and confirms that the last window starts at index n - k. That structure is independent of any algorithm you choose for computing the maximums and forms the base that every later solution uses.

In practice the data feeding this sliding window might be price ticks, sensor readings, or counts of active sessions over time. The array model still fits those situations, where each index stands for a time step or position, and the window collects a recent history of fixed length that feeds further logic or reporting.

Problem Setup For Sliding Window Maximum

Formalizing the input and output helps guide the rest of the code. The input is an integer array nums and a window length k, where k is a positive integer that does not exceed the array length. The output is another integer array that has one entry per valid window, with length n - k + 1. Each entry in the output holds the maximum value from the corresponding window in the input.

Many Java solutions expose this work through a method with a signature like this:

This signature says a lot about the problem setup without showing any implementation detail. The input array is not wrapped, there is no custom data structure for the window itself, and the result is delivered in a plain array that lines up with how the windows move through the original data. That style also matches common expectations in interview settings and library style helper methods.

You can add a small driver method that calls maxSlidingWindow and prints the result to keep the end goal in view while you think about algorithm choices:

This shell does not solve the problem yet, but it sets expectations about the result format. The caller passes an array and window length and receives a second array with one number per window. That mental picture stays the same whether you pick a naive method, a heap based method, or a deque based method.

Input scale matters just as much as the shape of the data. Small test cases with n around 10 or 20 permit slow scans that run in quadratic time without any trouble. Large arrays with n in the tens or hundreds of thousands expose performance problems quickly, especially when k is also large. The reason is that an O(n * k) scan spends too much time repeating work across windows that differ by only one element. The main goal of better algorithms is to reduce that repetition and reuse earlier work as the window slides.

Error handling and edge cases also belong in the basic setup. Arrays of length zero, negative k, and k larger than n either need to be rejected with an exception or mapped to neutral behavior such as returning an empty result array. Many implementations choose the second option and return an empty array when there are no valid windows, which keeps the code free of extra exception types and still prevents index problems.

Naive Solutions For The Window

Early attempts at sliding window maximums usually start with a direct nested loop. For every starting index of a window the code scans the next k elements, finds the maximum among them, writes that maximum to the result, then moves on to the next window. That nested scan visits many array entries again and again, which leads to O(n * k) time complexity. Space usage looks fine in that version, but the time cost grows too quickly when both n and k are large.

Here is a basic implementation of that brute force idea:

The nested loop is easy to read, and the logic matches the problem description closely. Performance is the main concern. Every window recomputes the maximum value from scratch, even though neighboring windows share nearly all their elements. With n around 100000 and k around 50000, this method must scan a very large number of entries, and those extra scans dominate total runtime.

Heap based solutions replace the inner loop with a heap, usually a max heap built from PriorityQueue with a custom comparator. That method keeps the current window’s elements in a priority queue and reads the maximum from the head of that queue. As the window moves, new elements are pushed into the heap and elements that leave the window are either removed directly or allowed to sit in the heap until they drift past the current window and get skipped.

One possible heap based version looks like this:

This version improves on the nested loop in many cases. Each insert into the heap and each removal costs O(log m) time, where m is the current heap size, so the worst case running time for this code is O(n log n). The heap always keeps the largest value for the window at the head, and stale entries are discarded when they rise to the top and their index falls to the left of the window start. Indexes travel with values inside the Entry records so the code can tell when a heap entry no longer belongs in the current window.

Performance is much better here than in the brute force scan, but the method still repeats more work than necessary. The heap structure keeps every element of the current window and maintains a very strong ordering that is more than the sliding window maximum problem needs. The deque based method trims that extra work down by storing indexes in increasing order and relying on a weaker, more targeted ordering between their values, which removes a large amount of overhead while keeping the result correct.

Deque Mechanics For Sliding Windows

Sliding window maximum with a deque turns the whole problem into a single left to right pass where only useful indexes stay in memory. The deque acts as a small, constantly updated view of candidates that still have a chance to be the maximum for the current window or for a window that will arrive shortly. Two ideas drive this behavior. Indexes stay in increasing order from front to back, and the values at those positions form a non-increasing sequence. With those properties in place, the front of the deque always points to the current maximum inside the active window.

Deque As A Window Helper

In Java, the Deque interface represents a double ended queue where elements can be added or removed at both ends. For sliding window maximum work, ArrayDeque<Integer> is the usual choice, because it stores elements in a resizable array and gives constant time for offerFirst, offerLast, pollFirst, and pollLast on average. LinkedList<Integer> also implements Deque, but node allocation and pointer chasing tend to slow things down in this scenario.

The deque does not store values directly. Instead, it keeps indexes that refer back into the nums array. This choice lets the code check both the value and its position in the window without duplicating data. Keeping indexes rather than values is what lets the algorithm drop entries that have moved out of the window range and entries that are blocked by a larger value.

One version of compact helper method that updates the deque for index i and array nums often looks like this:

This helper enforces the non-increasing sequence of values across the deque. Any index at the back with a value less than or equal to nums[i] gets removed, because index i will be a better candidate for every later window that contains both positions. The new index then takes its place at the back.

Full pass over an array can call this helper inside a loop and track the current maximum from the front. Let’s see a compact version that focuses on deque handling:

This version shows how the deque serves as a helper for the window. The front always holds the index of the maximum inside the current window, and the back is where new indexes are added after candidates with smaller values have been removed. Window bounds are tracked through windowStart, and the deque only contains indexes that lie inside the current window and that are not dominated by a larger value to their right.

Keeping Candidate Indexes In Order

Monotonic behavior inside the deque is what keeps the maximum easy to read. The word monotonic here refers to the sequence of values nums[idx] for indexes idx stored from front to back. That sequence never rises as you walk from front to back, so the largest number always sits at the front. Indexes themselves also increase from front to back, because every new index is larger than anything already in the deque, and stale entries at the front are removed as the window moves.

The heart of that behavior is the rule that removes dominated indexes from the back before inserting a new index. Such an index has a value less than or equal to the value at the new index and sits at an earlier position. That earlier position means both indexes can appear in the same future window, and the smaller value can never win while the larger one is present. Dropping dominated indexes as soon as the larger value arrives keeps the deque small and keeps future work low.

The same rule that DequeHelper.pushIndex follows also explains the running time. Each index is appended to the deque one time and removed at most one time, so the total number of deque operations across the whole run is proportional to n. That bounded work per index is why the deque method runs in linear time.

Short walkthrough makes the ordering rules easier to see. Take nums = [4, 2, 5, 1] and focus only on how the deque contents change as DequeHelper.pushIndex runs for each index.

At i = 0, the deque is empty, so index 0 enters and the deque holds [0]. At i = 1, value 2 is less than value 4 at index 0, so nothing gets removed, and 1 gets added at the back, giving [0, 1]. At i = 2, value 5 is larger than 2, so index 1 is removed. Value 5 is also larger than 4, so index 0 is removed as well, then index 2 is added, leaving [2]. That single index represents the largest value among everything seen so far. At i = 3, value 1 is smaller than 5, so no removal happens at the back, and index 3 gets appended. The deque now holds [2, 3], and the values at those positions, [5, 1], still form a non-increasing sequence.

Every future window that contains index 2 will have 5 as its maximum, until that index falls out of range on the left. Index 3 is only relevant for windows that no longer include index 2, because whenever both are present, the larger value 5 keeps the smaller value from mattering to the maximum.

Removing Stale Entries As The Window Moves

Stale entries are indexes in the deque that refer to elements that no longer belong to the current window. When the current index is i and the window length is k, the window covers indexes from i - k + 1 to i. Anything less than i - k + 1 lies outside that range and no longer counts toward the maximum. The deque stores indexes in increasing order from front to back, so the smallest index always sits at the front. That property makes stale removal very cheap. At each step you only need to compare the front index with the current windowStart. If the front index is smaller, it falls out of the window and can be removed. No other index in the deque can be smaller, so there is no need to scan through the rest.

One option for a method that handles stale removal and maximum extraction can look like this:

This helper assumes that a separate call has just added the current index i into the deque while preserving monotonic order for values. The first part removes a stale entry at the front if needed. The second part checks that a full window now exists and then writes the maximum to the result array by reading the value at deque.peekFirst().

Putting the stale removal rule and the ordering rule in combination gives a full loop where each index is added one time and removed one time. Every time the window advances by one step, exactly one new index appears on the right, and at most one old index drops off on the left from the front of the deque as it becomes stale. That behavior keeps memory usage low and keeps time spent per index constant on average.

Now let’s look at an example that focuses on these two steps can help tie things together:

The loop body mirrors the verbal rules. First, a check at the front removes any index that has moved out of the window. Second, a loop at the back removes dominated indexes, then the current index is added. Finally, when a full window is present, the maximum comes straight from the front of the deque. Every window gets processed with a small and predictable amount of work, and the deque evolves smoothly as the window slides along the array.

Conclusion

Deque based sliding window maximum in Java boils down to a very specific set of mechanics. The window walks across the array one index at a time, a deque stores only indexes, and two rules keep that deque useful. Values at stored indexes form a non-increasing sequence from front to back, so the front index always points to the current maximum, and any index with a smaller or equal value behind a larger one gets removed. At the same time, indexes that fall to the left of the window start are treated as stale and dropped from the front as the window moves. With those rules in place, every index is added and removed at most one time, which gives linear running time while still delivering the maximum for every window of size k.

1. Java Deque Interface Documentation

2. Java ArrayDeque Class Documentation

3. Java PriorityQueue Class Documentation

4. LeetCode Sliding Window Maximum Problem