leetcode-239 Sliding Window Maximum

[239] Sliding Window Maximum

Key Concept: Monotonic Deque - Use a deque to maintain indices of potential maximum elements in decreasing order. This allows O(1) access to the maximum in the current window.

Algorithm:

Remove indices outside the current window from the front
Remove indices with smaller values from the back (they can never be maximum)
The front of deque always contains the index of the maximum element

# You are given an array of integers nums and an integer k. There is a sliding
# window of size k which is moving from the left to the right. You can only see
# the k numbers in the window. 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
#
# Constraints:
# 1 <= nums.length <= 10^5
# -10^4 <= nums[i] <= 10^4
# 1 <= k <= nums.length

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Deque stores indices of elements in decreasing order of their values
        dq = deque()
        result = []

        for i in range(len(nums)):
            # Remove indices outside current window from front
            while dq and dq[0] < i - k + 1:
                dq.popleft()

            # Remove indices with smaller values from back
            # They can never be the maximum in current or future windows
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            dq.append(i)

            # Add maximum to result once we have a full window
            if i >= k - 1:
                result.append(nums[dq[0]])

        return result

# Time Complexity: O(n) - each element is added and removed at most once
# Space Complexity: O(k) - deque stores at most k elements