Question

Formatted question description: https://leetcode.ca/all/239.html

Level

Hard

Description

Given an array 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:

Input: nums = [1,3,-1,-3,5,3,6,7], and 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

Note:

You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:

Could you solve it in linear time?

Algorithm

Use a double-ended queue (deque) that allows insertion and deletion operations at both ends in O(1) time complexity. To maintain a sliding window of size k, store indices instead of actual numbers in the deque.

For the first k elements from nums, add them directly to the deque. Before adding each new element, compare it with the element at the back of the deque (if the last element in the deque is index i, the corresponding number is nums[i]). If the current number is greater, remove the last element from the deque. Continue this process until either the deque is empty or the last element in the deque is greater than or equal to the current number. The index of the maximum element in the first window of size k is at the front of the deque. Add this maximum element to the result array at index 0.

Then, iterate over nums starting from index k to the end. For each index i, first check if the first element in the deque equals i - k (which means it’s outside the current window) and remove it if necessary. Next, if the number corresponding to the last index in the deque is less than the current number, remove the last element from the deque. Repeat until the deque is empty or the number corresponding to the last element in the deque is greater than or equal to the current number. The index of the maximum element in the current window is at the front of the deque. Place this maximum element in the corresponding position of the result array.

Finally, return the result array.

Example Illustration:

Given the input: [1, 3, -1, -3, 5, 3, 6, 7]

Use a deque q with the right end for insertion and the left front for deletion.

iteration-1: q = [0]
iteration-2: q = [0, 1]
iteration-3: q = [0, 1, 2]
At iteration-4: Remove the front if it’s out of the window: q = [1, 2]. Keep removing from the back if the current number is greater: none. Add the current index: q = [1, 2, 3]. The maximum is nums[1].
At iteration-5: Check and remove the front if it’s out of the window: q = [2, 3]. Remove from the back if the current number is greater, resulting in: q = []. Then, add the current index: q = [4]. The maximum is nums[4].
iteration-6 to iteration-8: Follow the same procedure to update the deque and identify the maximum for each window, updating the result array accordingly.

Code

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<String> 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;
    }
}

// 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;
    }
};

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

func maxSlidingWindow(nums []int, k int) (ans []int) {
	q := []int{}
	for i, v := range nums {
		if len(q) > 0 && i-k+1 > q[0] {
			q = q[1:]
		}
		for len(q) > 0 && nums[q[len(q)-1]] <= v {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		if i >= k-1 {
			ans = append(ans, nums[q[0]])
		}
	}
	return ans
}

/**
 * @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;
};

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;
    }
}

use std::collections::VecDeque;

impl Solution {
    #[allow(dead_code)]
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        // The deque contains the index of `nums`
        let mut q: VecDeque<usize> = VecDeque::new();
        let mut ans_vec: Vec<i32> = Vec::new();

        for i in 0..nums.len() {
            // Check the first element of queue, if it's out of bound
            if !q.is_empty() && (i as i32 - k + 1) > *q.front().unwrap() as i32 {
                // Pop it out
                q.pop_front();
            }
            // Pop back elements out until either the deque is empty
            // Or the back element is greater than the current traversed element
            while !q.is_empty() && nums[*q.back().unwrap()] <= nums[i] {
                q.pop_back();
            }
            // Push the current index in queue
            q.push_back(i);
            // Check if the condition is satisfied
            if i >= (k - 1) as usize {
                ans_vec.push(nums[*q.front().unwrap()]);
            }
        }

        ans_vec
    }
}

239 - Sliding Window Maximum

Question

Level

Description

Algorithm

Example Illustration:

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Level

Description

Algorithm

Example Illustration:

Code

All Problems

All Solutions