Problem Statement in English

You’re given an array of integers nums, and an integer k. You need to find the maximum element in every window of size k in the array.

Approach

This is something that unless you’ve seen, you won’t be able to solve.

We use a queue to store the indices of the elements along with their values in the window.

We also ensure that the queue has elements in decreasing order of the values. This allows us to always get the maximum element in the window in constant time.

There are a couple other things to keep in mind, but I think it’s better we work our way through an example to understand the mechanics of this.

$k=2$, nums:

758

ans:

---

q:

---

At $r=0$:

nums:

758

ans:

---

q:

(0,7)--

Since the length of q is less than k, we don’t need to remove any elements.

At $r=1$:

nums:

758

ans:

-7-

q:

(0,7)(1,5)-

Since the length of q is equal to the value of $k$, we need to add something to ans.

At $r=2$:

nums:

758

ans:

-78

q:

(1,5)(2,8)

Since $8 > 5$, which is the rightmost element, we must first remove 5 before appending the new element.

Since the length of q is equal to the value of $k$, we need to add something to ans.

It’s ok if that didn’t make too much sense, try reading the code instead.

Solution in Python


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # if `k` is 1
        # we can't have any sliding window
        # and so the answer is the same as the input
        if k == 1:
            # return the input
            return nums

        # to store the final answer
        ans = []

        # in this dequeu
        # we store a tuple of:
        # - the index
        # - and the value at that index
        q: deque[tuple[int, int]] = deque()

        # iterate over the nums
        for r in range(nums):

            # if the length of the deque is equal to `k`
            # we need to remove the oldest element
            # because it is no longer in the window
            if len(q) == k:
                # remove the oldest (leftmost) element
                q.popleft()

            # while the deque is not empty
            # and the last element in the deque
            # is less than the current element
            # pointed to by the pointer
            while len(q) > 0 and q[-1][1] < nums[r]:
                # remove the last (rightmost) element
                q.pop()

            # add the current index along
            # with the value at that index to the deque
            q.append((r, nums[r]))

            # if we've finished the initial loading phase
            # where we start with an empty deque
            if r >= k - 1:
                # and the oldest element is outside the window
                while r - q[0][0] >= k:
                    # remove the oldest element
                    q.popleft()

                # the oldest element is within the window
                # so add it to the answer
                ans.append(q[0][1])

        # return the final answer
        return ans

Complexity

  • Time: $O(n)$
    Since we process $n$ elements at most.

  • Space: $O(n)$
    Since we store $n$ elements at most in the deque.

Mistakes I Made

I had to look this one up :(

And we are done.