Sliding Window Maximum

HARD

Description

You are given an array of integers nums, 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.

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Approaches

Checkout 2 different approaches to solve Sliding Window Maximum. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

For each window of size k, find the maximum element by iterating through all elements in the window.

Algorithm

Initialize result array of size (n-k+1)
For each window position i from 0 to n-k:
- Find maximum element in window nums[i] to nums[i+k-1]
- Store maximum in result[i]
Return result array

This approach involves using two nested loops. The outer loop iterates through each possible window position, and the inner loop finds the maximum element in the current window.

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    
    for (int i = 0; i <= n - 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;
}

Complexity Analysis

Time Complexity: O(n*k) where n is the length of array and k is window size - for each window we traverse k elementsSpace Complexity: O(1) excluding the output array - only constant extra space is used

Pros and Cons

Pros:

Simple to implement
No extra space required except for output array
Works well for small inputs

Cons:

Very inefficient for large arrays
Redundant comparisons as same elements are compared multiple times
Not suitable for real-time applications with large inputs

Code Solutions

Checking out 5 solutions in different languages for Sliding Window Maximum. Click on different languages to view the code.

using System.Collections.Generic ; public class Solution { public int [] MaxSlidingWindow ( int [] nums , int k ) { if ( nums . Length == 0 ) return new int [ 0 ]; var result = new int [ nums . Length - k + 1 ]; var descOrderNums = new LinkedList < int >(); for ( var i = 0 ; i < nums . Length ; ++ i ) { if ( i >= k && nums [ i - k ] == descOrderNums . First . Value ) { descOrderNums . RemoveFirst (); } while ( descOrderNums . Count > 0 && nums [ i ] > descOrderNums . Last . Value ) { descOrderNums . RemoveLast (); } descOrderNums . AddLast ( nums [ i ]); if ( i >= k - 1 ) { result [ i - k + 1 ] = descOrderNums . First . Value ; } } return result ; } }

Video Solution

Watch the video walkthrough for Sliding Window Maximum

Patterns:

Sliding Window

Data Structures:

ArrayHeap (Priority Queue)QueueMonotonic Queue

Companies:

Cisco |DoorDash |Flipkart |Goldman Sachs |