Sliding Window Maximum — LeetCode 239 Python Solution

The problem

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.

Example

Input

nums = [1,3,-1,-3,5,3,6,7], k = 3

Output

[3,3,5,5,6,7]

Explanation

Window position Max

Python solution

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-v, i) for i, v in enumerate(nums[: k - 1])]
        heapify(q)
        ans = []
        for i in range(k - 1, len(nums)):
            heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heappop(q)
            ans.append(-q[0][0])
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 239. Sliding Window Maximum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems