Problem of The Day: Sliding Window Maximum

3 min read 758 words

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_heap = []
        queue = deque()
        res = []
        for i, num in enumerate(nums):
            heapq.heappush(max_heap, (-num, -i))
            queue.append((num, i))
            if len(queue) > k:
                start, j = queue.popleft()
                max_heap.remove((-start, -j))
                heapq.heapify(max_heap)

            if len(queue) >= k:
                res.append(-max_heap[0][0])

        return res

Solution [Accepted]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_heap = [(-nums[i], i) for i in range(k)]
        heapq.heapify(max_heap)

        res = [-max_heap[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(max_heap, (-nums[i], i))
            while max_heap[0][1] <= i - k:
                heapq.heappop(max_heap)

            res.append(-max_heap[0][0])

        return res

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        List<int> result = new List<int>();
        var maxHeap = new PriorityQueue<(int,int), int>();
        for (var i = 0; i < k; i++) {
            maxHeap.Enqueue((nums[i], i), -nums[i]);
        }
        result.Add(maxHeap.Peek().Item1);

        for (var i = k; i < nums.Length; i++) {
            maxHeap.Enqueue((nums[i], i), -nums[i]);
            while (maxHeap.Peek().Item2 <= i - k) {
                maxHeap.Dequeue();
            }
            result.Add(maxHeap.Peek().Item1);
        }
        return result.ToArray();
    }
}

• time: O(Nlogk)
• space: O(N)

Editorial

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

        for i in range(k):
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)

        res.append(nums[dq[0]])

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

            dq.append(i)
            res.append(nums[dq[0]])

        return res