_239. Sliding Window Maximum.md

239. Sliding Window Maximum

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 04, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

Acceptance Rate : 47.11 %

---

Solutions

• h239 v1.py
• h239 v2.py

Python

h239 v1.py

# Extremly low space efficiency but it passes soooo (5% margine consistently)
# Runtime is similarly in the [0,25] region

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        numSlides = len(nums) - k + 1
        output = [0] * numSlides

        pastVals = []

        # initialization of first k values
        for i in range(k):
            heapq.heappush(pastVals, (-1 * nums[i], i))
            output[0] = pastVals[0][0] * -1
            

        for i in range(k, len(nums)) :
            heapq.heappush(pastVals, (-1 * nums[i], i))

            while (pastVals[0][1] < i - k + 1) :
                heapq.heappop(pastVals)

            output[i - k + 1] = -1 * pastVals[0][0]


        return output

h239 v2.py

# [40/50% region]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        numSlides = len(nums) - k + 1
        output = [0] * numSlides

        # indices of values to use
        dequeueuee = deque()

        # initializing the first bit of space with deque index records
        for i in range(0, k - 1) :
            if not dequeueuee :
                dequeueuee.append(i) 
                continue
            while dequeueuee and nums[dequeueuee[0]] <= nums[i] : 
                dequeueuee.popleft()
            dequeueuee.appendleft(i)
        
        # rest of it lol
        for i in range(k - 1, len(nums)) :
            while dequeueuee and dequeueuee[-1] < i - k + 1 :
                dequeueuee.pop()
            while dequeueuee and (dequeueuee[0] < i - k + 1 or nums[dequeueuee[0]] <= nums[i]) :
                dequeueuee.popleft()
            dequeueuee.appendleft(i)
            output[i - k + 1] = nums[dequeueuee[-1]]
        
        return output