Sliding Window Maximum Problem Solution

The sliding window maximum problem requires finding the maximum element in each contiguous subarray of a given size. This classic algorithmic challenge demonstrates efficient window management using deque data structures to achieve linear time complexity.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on input array size? (e.g., up to 10^6 elements)
2. Are duplicate values allowed in the input array?
3. Should I return a new array or can I modify the input array?
4. Can I mutate the input array during processing?
5. What is the target time complexity for follow-up? (e.g., O(n) or better)

Restatement of the pattern: The sliding window maximum problem involves finding the maximum element in each contiguous subarray (window) of a fixed size k within an array. Given an array of integers and a window size k, we need to return an array containing the maximum value from each sliding window as it moves from left to right across the input.

Signal words and constraint shape: Key indicators include "maximum in sliding window," "fixed-size window," "contiguous subarray," and "moving window." The constraint that a fixed-size window slides across the array is the defining characteristic.

Assumptions:

• The input array contains integers (positive, negative, or zero)
• Window size k is a positive integer less than or equal to the array length
• The result array should contain exactly (n - k + 1) elements where n is the input array length
• We're looking for a maximum value in each window, not minimum or other statistics

Scenario fit: This pattern is best suited for static scenarios where the entire input array is available. It's not ideal for streaming data where new elements arrive continuously, as the sliding window approach requires knowing the full context of the current window. The pattern works well for batch processing where we can process all elements at once.

The core insight is that we can avoid recomputing the maximum for every window from scratch by maintaining some form of ordering or tracking structure that allows us to efficiently update the maximum as we slide the window.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Maximum element in a sliding window of size k"
• "Find the largest values in each contiguous subarray of fixed size"
• "Window of fixed size moving across array"
• "Need to process elements in a fixed-size moving range"

Why this pattern fits better than alternatives: The sliding window maximum pattern is specifically optimized for problems where:

1. You need to find extremal values (max/min) over fixed-size contiguous subarrays
2. The window slides linearly across the input
3. You want to avoid recalculating the entire range's extremum at each step

Compared to brute force O(nk) approaches, this pattern leverages the overlapping nature of windows to achieve O(n) time complexity. Unlike general max-heap approaches that require maintaining all elements, this pattern uses specialized data structures like deques to maintain only relevant candidates.

Conditions where variations apply:

• For minimum instead of maximum, same pattern applies with min-deque
• When window size is variable (not fixed), use general sliding window techniques with hash maps or sets
• For streaming data where you can't see future elements, use online algorithms with bounded buffers

Core insight: The key insight is that when a window slides, many elements remain in the new window. We only need to track elements that could potentially become the maximum, and we can efficiently remove elements that are no longer candidates as the window moves. This is achieved by maintaining a monotonic deque where elements are in decreasing order, ensuring the front always contains the maximum of the current window.

The pattern works best when:

• Window size is fixed and known
• You're looking for extremal values over contiguous subarrays
• Input size is large enough that O(n) is significantly better than O(nk)
• You can afford the extra space for maintaining the deque structure

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I slide a window of size k across the array and find the maximum in each window - that would be O(n*k) time complexity. But that's inefficient because I'm recalculating the maximum for overlapping elements in each window.

Let me think about how to optimize this. I notice that if I maintain a data structure that can efficiently track the maximum element in a sliding window, I can reduce it to O(n) time. The key insight is that I don't need to recompute everything from scratch each time - I can leverage the fact that only one element is added and one is removed from the window at each step.

I think I can use a deque (double-ended queue) to maintain potential maximums in decreasing order. When a new element comes in, I remove all elements smaller than it from the back of the deque since they can never be maximum. When an element goes out of window, I remove it from the front if it's at the front. This way, the front of deque always contains the maximum for current window.

The invariant I'm maintaining is that the deque stores elements in decreasing order, and it only contains elements that could potentially be maximums for future windows.

Brute-force approach: The naive solution checks every window of size k by scanning all elements in that window to find the maximum. This is O(n*k) time complexity where n is array length. It's not ideal because:

• We do redundant work - many elements are scanned multiple times
• For large arrays, this becomes very inefficient
• We don't leverage the sliding nature of the problem

Improved approach: I'll use a deque to maintain potential maximums. The key optimization is:

• Maintain the deque in decreasing order so that front always has maximum
• When adding new element, remove all smaller elements from back before adding
• When removing old element, check if it's at front and remove if so
• This gives us O(n) time complexity since each element is added and removed at most once

Final approach with step-by-step reasoning:

1. Use a deque to store indices of array elements in decreasing order of their values
2. For first k elements, build the initial deque by removing smaller elements from back
3. Add maximum (front of deque) to result array
4. For remaining elements:
   • Remove indices that are out of current window from front
   • Remove all indices whose values are less than current element from back
   • Add current element index to deque
   • Add front of deque (maximum) to result array
5. The invariant maintained is that deque always contains indices in decreasing order of their values, and only valid candidates for maximum are kept

Important invariants that must hold:

• Deque stores indices in decreasing order of their corresponding array values
• All elements in deque are within current window bounds or will be valid soon
• Front of deque always represents maximum element in current window
• Elements are never added to deque that cannot possibly be maximum in any future window

4. Data Structure Choice

For the sliding window maximum problem, I'll use a deque (double-ended queue) as my primary data structure.

Primary Data Structures Used

1. ArrayDeque - Used as a monotonic deque to maintain potential maximums
2. Integer array - Input array, which we'll process element by element

Why Each Data Structure Is Needed

The ArrayDeque is essential because:

• It supports O(1) operations at both ends (add/remove from front and back)
• It maintains elements in decreasing order (monotonic property)
• It allows us to efficiently remove elements that are no longer relevant as the window slides
• It's perfect for maintaining a "sliding window" of indices where values are in decreasing order

The input array is needed because:

• It contains the actual elements we need to process
• We iterate through it once to build our result

Time and Space Impact

Time Complexity:

• Deque operations: O(1) amortized
• Array traversal: O(n)
• Overall: O(n)

Space Complexity:

• Deque can hold at most n elements in worst case: O(n)
• Result array: O(n-k+1)
• Overall: O(n)

Helper Structure for Simplification

I use a custom helper method to encapsulate the deque maintenance logic:

• Keeps the deque in decreasing order by removing smaller elements from back
• Removes outdated indices that are outside current window
• This abstraction makes the main algorithm cleaner and more readable

The deque approach is superior to a simple queue because it maintains the monotonic property that allows us to always access the maximum in O(1) time, rather than having to scan the entire window each time.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3

Step-by-step execution:

1. Initial window [0,2]: nums = [1,3,-1]

   • Our deque maintains indices in decreasing order of values: [1,0,2] (values: 3,1,-1)
   • Maximum for this window is nums[1] = 3
   • Result so far: [3]

2. Slide to window [1,3]: nums = [3,-1,-3]

   • Remove index 0 (value 1) since it's outside window
   • Add index 3 (value -3) to deque maintaining decreasing order: [1,3,2] (values: 3,-3,-1)
   • Maximum is still nums[1] = 3
   • Result so far: [3,3]

3. Slide to window [2,4]: nums = [-1,-3,5]

   • Remove index 1 (value 3) since it's outside window
   • Add index 4 (value 5) to deque maintaining decreasing order: [4,2,3] (values: 5,-1,-3)
   • Maximum is nums[4] = 5
   • Result so far: [3,3,5]

4. Slide to window [3,5]: nums = [-3,5,3]

   • Remove index 2 (value -1) since it's outside window
   • Add index 5 (value 3) to deque maintaining decreasing order: [4,5,3] (values: 5,3,-3)
   • Maximum is nums[4] = 5
   • Result so far: [3,3,5,5]

5. Slide to window [4,6]: nums = [5,3,6]

   • Remove index 3 (value -3) since it's outside window
   • Add index 6 (value 6) to deque maintaining decreasing order: [6,4,5] (values: 6,5,3)
   • Maximum is nums[6] = 6
   • Result so far: [3,3,5,5,6]

6. Slide to window [5,7]: nums = [3,6,7]

   • Remove index 4 (value 5) since it's outside window
   • Add index 7 (value 7) to deque maintaining decreasing order: [7,6,5] (values: 7,6,3)
   • Maximum is nums[7] = 7
   • Final result: [3,3,5,5,6,7]

Edge case handling:

• Empty input array returns empty result
• When window size equals array size, we return the maximum element in the entire array
• The deque ensures we never look at elements outside our current window

Why termination is guaranteed: The algorithm processes each element exactly once, and the deque operations maintain the necessary invariants. The sliding window moves from left to right, and we always have a valid maximum for the current window by looking at the front of our deque.

6. Java Solution

import java.util.*;

public class SlidingWindowMaximum {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        // Deque to store indices of array elements
        // Elements in deque are in decreasing order (max at front)
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        int resultIndex = 0;
        
        // Process first k elements
        for (int i = 0; i < k; i++) {
            // Remove elements smaller than current element from back
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        
        // Store max of first window
        result[resultIndex++] = nums[deque.peekFirst()];
        
        // Process remaining elements
        for (int i = k; i < nums.length; i++) {
            // Remove elements outside current window from front
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            
            // Remove elements smaller than current element from back
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            
            // Add current element index to deque
            deque.offerLast(i);
            
            // Store max of current window
            result[resultIndex++] = nums[deque.peekFirst()];
        }
        
        return result;
    }
}

This solution uses a deque to maintain indices of array elements in decreasing order. The front of the deque always contains the index of the maximum element in the current sliding window. For each new element, we remove indices that are out of the window range and elements smaller than the current element from the back, ensuring the deque maintains its decreasing property.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm processes each element in the input array exactly twice - once when adding to the deque and once when removing from the deque. Even though there are nested operations, each element is added and removed at most once from the deque, resulting in an amortized O(1) operation per element.

Space Complexity: O(k)

The deque stores at most k elements at any time, where k is the window size. In the worst case, when all elements in a window are distinct and in decreasing order, the deque will contain up to k elements. The result array uses O(n - k + 1) space, but this is dominated by the deque's space usage.

Why these bounds are correct:

The key insight is that while we might have nested loops in our code, the total number of operations across all iterations remains linear. Each element is processed at most twice - once when it's added to the deque and once when it's removed. This is the essence of amortized analysis for sliding window problems.

The solution is optimal because:

1. We must examine each element at least once to determine if it's the maximum in its window
2. We cannot avoid the O(k) space requirement for maintaining the sliding window state
3. The linear time complexity matches the theoretical lower bound for this problem

The solution is near-optimal as it achieves the best possible time complexity for this problem type, with no known O(n) solution that's faster than our approach.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• Empty array: Handle gracefully with empty result list or throw appropriate exception
• Single element: Window size of 1 should return the array itself, window size > 1 should return empty list
• Window size 0: Should be handled as invalid input (typically throw exception or return empty list)

Duplicate values and repeated states

• All identical elements: The algorithm must properly handle duplicate maximum values in the sliding window
• Repeated maximums: When a new element enters and becomes the new maximum, we must correctly update our tracking structure

Boundary conditions

• Window size equals array length: Should return the maximum of the entire array as a single result
• Window size larger than array length: Should return empty list since no valid windows exist
• Array with negative numbers: The sliding window logic must work correctly with all negative values

Common implementation mistakes

• Incorrect index tracking: Confusing window boundaries with actual array indices, particularly when using a deque
• Not maintaining proper window bounds: Failing to remove elements that are outside the current window range from the deque
• Incorrect deque state management: Not properly removing elements that are no longer candidates for maximum (e.g., removing from front when they're still valid)
• Off-by-one errors: Mismanaging the window size and array bounds in loop conditions
• Not handling monotonic property correctly: When maintaining a decreasing deque, failing to properly clean up elements that are no longer useful

Implementation-specific pitfalls

• Deque vs. ArrayList: Using ArrayList for window tracking instead of Deque, leading to O(n) removal operations
• Memory leaks: Not properly cleaning up deque elements when they exit the window, potentially causing memory issues with large arrays
• Race conditions in multi-threaded scenarios: If this is used in concurrent contexts, the sliding window logic must be thread-safe

9. Alternative Approaches

There are several alternative approaches to solving the sliding window maximum problem, each with different trade-offs:

1. Brute Force with Priority Queue Instead of maintaining a deque, we could use a max heap (PriorityQueue) to track elements in the current window. For each new element, we add it to the heap and remove elements that are outside the window bounds. However, this approach has O(n log n) time complexity due to heap operations and doesn't maintain the sliding window property efficiently.

2. Segment Tree Approach We could build a segment tree where each node stores the maximum value in its range. For each window, we query the maximum in the range [i, i+k-1]. This gives O(n log n) time complexity but requires more complex implementation and additional space for the segment tree structure.

3. Sparse Table with Range Maximum Query Precompute a sparse table that allows O(1) range maximum queries. This approach works well for static arrays but requires O(n log n) preprocessing time and space, making it unsuitable when the window slides dynamically.

4. Monotonic Queue with Deque (Optimal) The deque-based approach is superior because it maintains a monotonic decreasing sequence of indices, ensuring each element is added and removed at most once. This results in O(n) time complexity with clean, readable code.

The deque solution is preferred because it's simpler to implement correctly than segment trees or sparse tables, and it achieves the optimal linear time complexity that's impossible to beat for this problem. The key insight is that we only need to keep track of elements that could potentially be the maximum in future windows, which is exactly what the monotonic deque achieves.

10. Test Cases

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // stores indices
        
        // Initialize the deque for first window
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        
        result[0] = nums[deque.peekFirst()];
        
        // Process remaining windows
        for (int i = k; i < nums.length; i++) {
            // Remove elements outside the window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            
            // Remove smaller elements from the back
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            result[i - k + 1] = nums[deque.peekFirst()];
        }
        
        return result;
    }
}

Sample Test Cases

Example 1: Basic case

int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
// Expected: [3, 3, 5, 5, 6, 7]
// Window 1: [1,3,-1] → max = 3
// Window 2: [3,-1,-3] → max = 3  
// Window 3: [-1,-3,5] → max = 5
// Window 4: [-3,5,3] → max = 5
// Window 5: [5,3,6] → max = 6
// Window 6: [3,6,7] → max = 7

Example 2: All negative numbers

int[] nums = {-1, -2, -3, -4, -5};
int k = 2;
// Expected: [-1, -2, -3, -4]
// Each window of size 2 has the larger (less negative) element

Example 3: Single element window

int[] nums = {5, 4, 3, 2, 1};
int k = 1;
// Expected: [5, 4, 3, 2, 1]
// Each window of size 1 is just the element itself

Example 4: Increasing sequence

int[] nums = {1, 2, 3, 4, 5};
int k = 3;
// Expected: [3, 4, 5]
// Each window of size 3 has the maximum at the end

Example 5: Empty array

int[] nums = {};
int k = 1;
// Expected: []

Example 6: Window size equals array length

int[] nums = {1, 2, 3};
int k = 3;
// Expected: [3]

Example 7: Duplicate maximums

int[] nums = {1, 2, 1, 2, 1};
int k = 2;
// Expected: [2, 2, 2]
// Multiple windows have the same maximum value of 2

11. Final Summary

The sliding window maximum problem is efficiently solved using a deque-based approach that maintains potential maximums in decreasing order, achieving optimal O(n) time complexity by processing each element exactly twice. This solution works by leveraging the deque's ability to efficiently maintain and update the maximum value as the window slides, making it ideal for scenarios where we need to quickly identify the largest element in a moving window of fixed size. The key insight is that we can discard elements smaller than the current element and elements outside the window bounds, ensuring optimal performance while maintaining clean, readable code structure.