Scale Engineer

Sliding Window Maximum

Hard
#0227Time: O(n*k) where n is the length of array and k is window size - for each window we traverse k elementsSpace: O(1) excluding the output array - only constant extra space is used30 companies
Patterns
Sliding Window
Data structures
ArrayHeap (Priority Queue)QueueMonotonic Queue
Companies
CiscoDoorDashFlipkartGoldman Sachs

Prompt

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 <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

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

Algorithm

  1. Initialize result array of size (n-k+1)
  2. 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]
  3. Return result array

Walkthrough

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

Time

O(n*k) where n is the length of array and k is window size - for each window we traverse k elements

Space

O(1) excluding the output array - only constant extra space is used

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem