Sliding Window Maximum

---

Sliding Window Maximum: 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^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

---

Try this Problem on your own or check similar problems:

1. Minimum Window Substring
2. Maximum Number of Robots Within Budget

Solution:

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    Deque<Integer> d = new LinkedList<>();

    for(int i = 0; i < nums.length; ++i){
      if (!d.isEmpty() && d.peekFirst() < i - k + 1) {
        d.pollFirst();
      }
      while (!d.isEmpty() && nums[i] >= nums[d.peekLast()]) {
        d.pollLast();
      }
      d.addLast(i);

      if (i - k + 1 >= 0) {
        result[i - k + 1] = nums[d.peekFirst()];
      }
    }

    return result;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const result = [];
  const deque = [];

  for (let i = 0; i < nums.length; i++) {
    if (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }
    while (deque.length > 0 && nums[i] >= nums[deque[deque.length - 1]]) {
      deque.pop();
    }
    deque.push(i);

    if (i - k + 1 >= 0) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
};

Python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        dq = deque()

        for i in range(len(nums)):
            if dq and dq[0] < i - k + 1:
                dq.popleft()
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)

            if i - k + 1 >= 0:
                result.append(nums[dq[0]])

        return result

C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;

        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);

            if (i - k + 1 >= 0) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(k)

---

Explanation:

The Deque is good data structure to use here since if we assume double linked list implementation it offers O(1) insertion/deletion both at head and tail. Since we use an auxiliary data structure, we have linear space complexity and linear time complexity (we at most traverse all elements in input array). There will be n-k+1 sliding windows where n is the size of input array, k is the size of input array, so we have to create a result array of that size where we will store the maximum elements of each window. We iterate over all elements in array and while doing it there are two operations that make the algorithm work:

• First, we discard the index (element in the deque) that is not in the current window (index < i - k + 1), if the window is ending at i and has the size of k, it's start will be at index i - k + 1, so any index before it should be discarded.
• Before adding a new index (shifting the window to the right side), we should also delete any index in dequeue which corresponds to an element in array that's smaller than the element at index we're trying to insert (the end of new window). Why do we do this? Well, the smaller numbers will never be the best candidate to be the maximum of the window since the new element is larger.
• i - k + 1 >= 0 checks if we have iterated over enough elements to form a valid window of size k. The time complexity is linear and proportional to the length of input array, while for our helper data structure we can have at most k elements in it (window size) leading to O(k) space complexity.