Problem Statement:
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.
Examples:
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] <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Approach
- Initialize:
res[]to store result.q[]to store elements in decreasing order (front always holds the max).- Two pointers:
i(window start) andj(window end).
- Traverse the array:
- Remove elements from the back of the queue if they are smaller than current
(arr[j]), since they can't be max. - Add
arr[j]to the queue. - When window size k is hit
(j >= k - 1):- Push the front of the queue to
res(it's the current max). - If the element going out of the window (arr[i]) is equal to the front of the queue,
remove it(q.shift()). - Move window ahead by incrementing
i.
- Push the front of the queue to
- Remove elements from the back of the queue if they are smaller than current
- Return the result array res.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: arr = [1,3,-1,-3,5,3,6,7], k = 3
Initialize: → res = [] → q = [] → i = 0, j = 0 Start sliding window loop: j = 0 → arr[j] = 1 → q = [] (empty) → push 1 → q = [1] j = 1 → arr[j] = 3 → 3 > 1 → pop 1 → q = [] → push 3 → q = [3] j = 2 → arr[j] = -1 → -1 not greater than 3 → push -1 → q = [3, -1] → j >= k-1 (2 >= 2): window formed → push q[0] = 3 to res → res = [3] → arr[i] == q[0]? → arr[0] = 1 ≠ 3 → don't shift q → i++ j = 3 → arr[j] = -3 → -3 not greater than -1 → push -3 → q = [3, -1, -3] → j >= k-1 → push q[0] = 3 → res = [3, 3] → arr[1] = 3 == q[0] → shift q → q = [-1, -3] → i++ j = 4 → arr[j] = 5 → 5 > -3 → pop -3 → 5 > -1 → pop -1 → q = [] → push 5 → q = [5] → j >= k-1 → push q[0] = 5 → res = [3, 3, 5] → arr[2] = -1 ≠ 5 → don't shift q → i++ j = 5 → arr[j] = 3 → 3 not greater than 5 → push 3 → q = [5, 3] → j >= k-1 → push q[0] = 5 → res = [3, 3, 5, 5] → arr[3] = -3 ≠ 5 → don't shift q → i++ j = 6 → arr[j] = 6 → 6 > 3 → pop 3 → 6 > 5 → pop 5 → q = [] → push 6 → q = [6] → j >= k-1 → push q[0] = 6 → res = [3, 3, 5, 5, 6] → arr[4] = 5 ≠ 6 → don't shift q → i++ j = 7 → arr[j] = 7 → 7 > 6 → pop 6 → q = [] → push 7 → q = [7] → j >= k-1 → push q[0] = 7 → res = [3, 3, 5, 5, 6, 7] → arr[5] = 3 ≠ 7 → don't shift q → i++ End of loop
Output: Result: [3, 3, 5, 5, 6, 7]
Visualisation:
var maxSlidingWindow = function(arr, k) {
let res = [];
let q = [];
let i = j = 0;
while (j < arr.length) {
while (q.length && arr[j] > q[q.length - 1]) {
q.pop();
}
q.push(arr[j]);
if (j >= k - 1) {
res.push(q[0]);
if (arr[i] == q[0]) q.shift();
++i;
}
++j;
}
return res;
};
from collections import deque
def maxSlidingWindow(arr, k):
res = []
q = deque()
sc
i = j = 0
while j < len(arr):
while q and arr[j] > q[-1]:
q.pop()
q.append(arr[j])
if j >= k - 1:
res.append(q[0])
if arr[i] == q[0]:
q.popleft()
i += 1
j += 1
return res
import java.util.*;
public class Solution {
public static List maxSlidingWindow(int[] arr, int k) {
List res = new ArrayList<>();
Deque q = new LinkedList<>();
int i = 0, j = 0;
while (j < arr.length) {
while (!q.isEmpty() && arr[j] > q.peekLast()) {
q.pollLast();
}
q.offerLast(arr[j]);
if (j >= k - 1) {
res.add(q.peekFirst());
if (arr[i] == q.peekFirst()) q.pollFirst();
i++;
}
j++;
}
return res;
}
}
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector maxSlidingWindow(vector& arr, int k) {
vector res;
deque q;
int i = 0, j = 0;
while (j < arr.size()) {
while (!q.empty() && arr[j] > q.back()) {
q.pop_back();
}
q.push_back(arr[j]);
if (j >= k - 1) {
res.push_back(q.front());
if (arr[i] == q.front()) q.pop_front();
i++;
}
j++;
}
return res;
}
#include <stdio.h>
#define MAX 10000
void maxSlidingWindow(int arr[], int n, int k) {
int res[MAX];
int q[MAX], front = 0, rear = -1;
int i = 0, j = 0, idx = 0;
while (j < n) {
while (rear >= front && arr[j] > q[rear]) {
rear--;
}
q[++rear] = arr[j];
if (j >= k - 1) {
res[idx++] = q[front];
if (arr[i] == q[front]) front++;
i++;
}
j++;
}
for (int m = 0; m < idx; m++)
printf("%d ", res[m]);
}
using System;
using System.Collections.Generic;
class Solution {
public static IList MaxSlidingWindow(int[] arr, int k) {
List res = new List();
LinkedList q = new LinkedList();
int i = 0, j = 0;
while (j < arr.Length) {
while (q.Count > 0 && arr[j] > q.Last.Value) {
q.RemoveLast();
}
q.AddLast(arr[j]);
if (j >= k - 1) {
res.Add(q.First.Value);
if (arr[i] == q.First.Value) q.RemoveFirst();
i++;
}
j++;
}
return res;
}
}
