[Leetcode] Sliding Window Maximum

239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size kwhich is moving from the very left of the array to the very right. You can only see the knumbers 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

How to approach?

First Approach

function maxSlidingWindow(nums: number[], k: number): number[] {
    let ans = []
    for (let i = 0; i < nums.length; i++) {
        let subArray = []
        for (let j = i; j < i + k; j++) {
            if (i < nums.length - k + 1) {
                subArray.push(nums[j])
            }
        }
        if (subArray.length != 0) {
            let max = Math.max(...subArray)
            ans.push(max)
        }
    }
    return ans
};

TLE error

Monotonic Deque

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] === i - k) {
      dq.shift();
    }

    while (dq.length && nums[i] >= nums[dq[dq.length - 1]]) {
      dq.pop();
    }

    dq.push(i);

    if (i >= k - 1) {
      res.push(nums[dq[0]]); 
    }
  }

  return res;
}

1. create dq and res to store the indices of nums and max value in the k length window on nums array.
2. create for loop starting from 0.
3. when dq has length and the first element equals i-k then its first element will be gone. since it means the index is out of the sliding window.
4. create while condition to check if the current element in nums is bigger/same than dq's last element index in nums. if it's bigger/same then pop the last element out in dq. because it's useless to use it for the max element in the sliding window.
5. after clean the dq, put the current index into dq.
6. when i is bigger/same than k-1, push the biggest element in current window using dq element index into res array. i should be bigger or same than k-1, why? because it will keep the valid window length.
7. lastly return the res.

summary

this way using monotonic deque(decreasing) to use the O(1) computation to find the max value in the current window. Time complexity will be O(n) since it checks element in nums one by one (adding or removing) for deque.