# Sliding Window Maximum **Difficulty:** HARD [External](https://leetcode.com/problems/sliding-window-maximum) Canonical: https://scaleengineer.com/dsa/problems/sliding-window-maximum **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue **Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Visa](https://scaleengineer.com/companies/visa), [tcs](https://scaleengineer.com/companies/tcs), [Coupang](https://scaleengineer.com/companies/coupang), [Juspay](https://scaleengineer.com/companies/juspay), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Zenefits](https://scaleengineer.com/companies/zenefits), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Wayfair](https://scaleengineer.com/companies/wayfair), [Zepto](https://scaleengineer.com/companies/zepto), [oyo](https://scaleengineer.com/companies/oyo), [Booking.com](https://scaleengineer.com/companies/booking.com), [Gojek](https://scaleengineer.com/companies/gojek), [Rubrik](https://scaleengineer.com/companies/rubrik), [MongoDB](https://scaleengineer.com/companies/mongodb), [Roku](https://scaleengineer.com/companies/roku), [LINE](https://scaleengineer.com/companies/line), [Nuro](https://scaleengineer.com/companies/nuro), [Gameskraft](https://scaleengineer.com/companies/gameskraft) --- ## Problem 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 ## Brute Force Approach For each window of size k, find the maximum element by iterating through all elements in the window. **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 **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 ### Explanation 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. ```java 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; } ``` ### 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 ## Deque (Double-ended Queue) Approach Use a deque to maintain indices of potential maximum elements in decreasing order. The front of deque always contains the maximum element's index for current window. **Time:** O(n) where n is the length of array - each element is processed exactly once · **Space:** O(k) where k is the window size - deque can contain at most k elements **Pros:** Optimal time complexity O(n); Each element is pushed and popped at most once; Maintains only useful elements in the deque **Cons:** Requires extra space for deque; Implementation is more complex than brute force; Deque operations might have overhead for very small inputs ### Explanation This approach uses a deque to store indices of elements that could be maximum for some window. We maintain the deque such that elements are in decreasing order and remove elements that are out of the current window. ```java public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; Deque deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // Remove elements outside current window while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // Remove smaller elements from back while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); // Add to result if we have a valid window if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; } } return result; } ``` ### Algorithm 1. Initialize deque and result array 2. For each element index i in array: - Remove indices from deque front if they're outside current window - Remove indices from deque back if their elements are smaller than current - Add current index to deque - If window is complete, add maximum (front of deque) to result 3. Return result array # Solutions ### CSharp ```csharp 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 ; } } ``` ### Java ```java import java.util.ArrayDeque ; import java.util.Arrays ; import java.util.Deque ; public class Sliding_Window_Maximum { public static void main ( String [] args ) { Sliding_Window_Maximum out = new Sliding_Window_Maximum (); Solution s = out . new Solution (); System . out . println ( Arrays . toString ( s . maxSlidingWindow ( new int []{ 1 , 3 ,- 1 ,- 3 , 5 , 3 , 6 , 7 }, 3 ))); } /* Deque dq = new ArrayDeque<>(); dq.offer("a"); dq.offer("b"); dq.offer("c"); System.out.println(dq.peek()); // a System.out.println(dq.peekFirst()); // a System.out.println(dq.peekLast()); // c */ class Solution { public int [] maxSlidingWindow ( int [] nums , int k ) { if ( nums == null || nums . length == 0 ) { return new int [ 0 ]; } int n = nums . length ; int [] result = new int [ n - k + 1 ]; int resultPointer = 0 ; // store index of nums array // q is descending values (its indexes) // eg. [6,5,4,3,2,1], q will be: [6,5,4], then [5,4,3], then [4,3,2], then [3,2,1] Deque < Integer > q = new ArrayDeque <>(); for ( int i = 0 ; i < nums . length ; i ++) { // remove index not in k-window while (! q . isEmpty () && q . peek () < i - k + 1 ) { // peek() head of queue q . poll (); } // remove use-less index in q while (! q . isEmpty () && nums [ q . peekLast ()] < nums [ i ]) { // peekLast() last of queue q . pollLast (); } q . offer ( i ); // start from k-th element, there is a max for window if ( i >= k - 1 ) { result [ resultPointer ] = nums [ q . peek ()]; resultPointer ++; } } return result ; } } } ############ class Solution { public int [] maxSlidingWindow ( int [] nums , int k ) { int n = nums . length ; int [] ans = new int [ n - k + 1 ]; Deque < Integer > q = new ArrayDeque <>(); for ( int i = 0 , j = 0 ; i < n ; ++ i ) { if (! q . isEmpty () && i - k + 1 > q . peekFirst ()) { q . pollFirst (); } while (! q . isEmpty () && nums [ q . peekLast ()] <= nums [ i ]) { q . pollLast (); } q . offer ( i ); if ( i >= k - 1 ) { ans [ j ++] = nums [ q . peekFirst ()]; } } return ans ; } } ``` ### JavaScript ```javascript /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function (nums, k) { let ans = []; let q = []; for (let i = 0; i < nums.length; ++i) { if (q && i - k + 1 > q[0]) { q.shift(); } while (q && nums[q[q.length - 1]] <= nums[i]) { q.pop(); } q.push(i); if (i >= k - 1) { ans.push(nums[q[0]]); } } return ans; }; ``` ### Python ```python from collections import deque class Solution : def maxSlidingWindow ( self , nums : List [ int ], k : int ) -> List [ int ]: q = deque () ans = [] for i , v in enumerate ( nums ): if q and i - k + 1 > q [ 0 ]: q . popleft () # remove index if out of window left while q and nums [ q [ - 1 ]] <= v : # `<=`, not `<`, to ensure the bigger index stored in deque q . pop () q . append ( i ) if i >= k - 1 : ans . append ( nums [ q [ 0 ]]) return ans ############ class Solution ( object ): def maxSlidingWindow ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: List[int] """ if k == 0 : return [] ans = [ 0 for _ in range ( len ( nums ) - k + 1 )] stack = collections . deque ([]) for i in range ( 0 , k ): while stack and nums [ stack [ - 1 ]] < nums [ i ]: stack . pop () stack . append ( i ) ans [ 0 ] = nums [ stack [ 0 ]] idx = 0 for i in range ( k , len ( nums )): idx += 1 if stack and stack [ 0 ] == i - k : stack . popleft () while stack and nums [ stack [ - 1 ]] < nums [ i ]: stack . pop () stack . append ( i ) ans [ idx ] = nums [ stack [ 0 ]] return ans ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/sliding-window-maximum/ // Time: O(N) // Space: O(N) class Solution { public: vector < int > maxSlidingWindow ( vector < int >& A , int k ) { vector < int > ans ; deque < int > q ; for ( int i = 0 ; i < A . size (); ++ i ) { if ( q . size () && q . front () == i - k ) q . pop_front (); while ( q . size () && A [ q . back ()] <= A [ i ]) q . pop_back (); q . push_back ( i ); if ( i >= k - 1 ) ans . push_back ( A [ q . front ()]); } return ans ; } }; ```