239. Sliding Window Maximum

Hard LeetCode

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 and max values are:

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]
Explanation: The window contains only one element, which is the maximum.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

How to solve the problem

• Brute Force Sliding Window O(n*k)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k:int) -> List[int]:
        left = 0
        result = []
        for right in range(k-1 ,len(nums)):
            current = max(nums[left:right+1])
            result.append(current)
            left +=1
        return result

• Monotonic Deque O(n)

python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k:int) -> List[int]:
        left = 0
        dq = deque()
        result = []
        for right, num in enumerate(nums):
            # remove indices whose values are smaller (or equal) than current num
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            dq.append(right)
            # remove the front index in dq if out of window
            if dq[0] < left:
                dq.popleft()
            # collect the max result for current window
            if right >= k - 1:
                result.append(nums[dq[0]])
                left += 1
        return result

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int left = 0;
        List<Integer> result = new ArrayList<>();
        for (int right = 0; right < nums.length; right++) {
            while (!dq.isEmpty() && nums[dq.getLast()] < nums[right]) {
                dq.removeLast();
            }
            dq.addLast(right);
            if (dq.getFirst() < left) {
                dq.removeFirst();
            }
            if (right >= k - 1) {
                result.add(nums[dq.getFirst()]);
                left += 1;
            }
        }
        int[] resultInt = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultInt[i] = result.get(i);
        }
        return resultInt;
    }
}

Complexity

• Brute Force: Time complexity: O(n*k), Space complexity: O(1) - Where n is the length of the array and k is the window size. We find the maximum in each window.
• Monotonic Deque: Time complexity: O(n), Space complexity: O(k) - Each element is added and removed from the deque at most once.