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. Each time the sliding window moves right by one position.

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**

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 105
-10**4 <= nums[i] <= 10**4
1 <= k <= nums.length

Solve¶

Re-run sum every time¶

This is a TLE solution

There isn’t much thing to said, still I try to do some thing cleaver:

We use a circle to store the current sliding window
The max function O(k) is call only if the added number is smaller than replace value and replace value is our current maximum number

Time Submitted	Status	Runtime	Memory	Language
08/16/2023 18:17	Time Limit Exceeded	N/A	N/A	python3

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        circle = nums[:k]
        currMax = max(circle)
        res = [currMax]
        index = 0
        rerun = False
        for v in nums[k:]:
            if circle[index] == currMax:
                rerun = True
            if v >= currMax:
                rerun = False
                currMax = v
            circle[index] = v
            if rerun:
                rerun = False
                currMax = max(circle)

            res.append(currMax)
            index += 1
            index %= k
        return res

Min-max tree¶

A good close to O(log n) time complexity to find any Maximum number in any range. The process is that we build and storing divide by 2 of the array maximum

array:  1 2 3 4 5 6 7 8
tree :  [2] [4] [6] [8]
        [  4  ] [  8  ] 
        [      8      ]

We then travel through and comparing all node that covering [x, y] range

Time Submitted	Status	Runtime	Memory	Language
08/16/2023 23:24	Accepted	8451 ms	352 MB	python3

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        cache = {}
        # inclusive
        def buildCache(l, r):
            if l == r:
                cache[(l,r)] = nums[l]
            else:
                m = (l + r) // 2
                buildCache(l, m)
                buildCache(m+1, r)
                cache[(l,r)] = max(cache[(l,m)], cache[(m+1,r)])
        buildCache(0, len(nums) - 1)

        def getCache(x, y, l=0, r=len(nums)-1):
            if (y < l) or (r < x):
                return -100000
            if (x <= l <= r <= y):
                return cache[(l,r)]

            m = (l + r) // 2
            return max(getCache(x,y, l,m), getCache(x,y, m+1,r))

        res = []
        for i in range(len(nums)-k+1):
            res.append(getCache(i, i+k-1))

        return res

Priority Queue with random access update¶

Another good close to O(log n) time complexity that creating a Heap to easily find Maximum number.

The process is that we build a modified heap with a replace that can access the last insert number and replace it with the next number, base on:

A cycle, fixed size array, that use to mimic the current sliding window. In the implement already remove that.
A heap self.heap
Array possition that index i store the position of heap element i in array. Or array[i] == heap[pos[i]]
Array revertPossition that index i store the position of array element i in the heap. Or array[revPos[i]] == heap[i]

Example:

index  [1, 2, 3, 4, 5, 6, 7, 8]
---
nums   [1, 9, 8, 4, 4, 3, 2, 5, 1, 3 , ...
array  [1, 9, 8, 4, 4, 3, 2, 5]
heap   [9, 5, 8, 4, 4, 3, 2, 1]
pos    [2, 8, 3, 4, 5, 6, 7, 1]
revPos [8, 1, 3, 4, 5, 6, 7, 2]

Explain:

Element 9 have position 1 in the heap, but have the position 2 in the array; So its possition is 2
Element 1 have position 1 in the array, but have the position 1 in the array; So its revertPossition is 8

So, when we update our sliding window array. We remove the last insert next element of cycle, fixed size array, change it to new value v of the next number in nums array. While doing so, we update:

heap: Replacing heap[revPos[next]] with new value v
We then update the heap base on v value (go up or down in the heap). We also keep track of pos and revPos change by swapping them correspond with heap element position change:
- swap(pos[parrent], pos[child]) : Basic swaping
- swap(revertPos[ pos[child] ], self.revertPos[ pos[parrent] ]) : Advantage swap, took me too long when trying to done the revertPos array directly (no pos array). After lot of trial and error, I have to go back to this implementation for simplicity.

It took quite some time to reimplement heap, quite great that I can done it.

The Heap data structure is implement base on array. To reduce the complexity of the calculation I use array [1..n] by padding all of my array with element [0] (as array in python start at 0)

Start at node x in the heap, we can access

To get parent node: x//2 (if x != 1)
To get child node: x*2 , x*2 + 1 (if them inside the heap)

The heap have fixed size, and the update is change directly on one of heap node, so we only implement up, down function to update the element position after change.

The main component is keep track of next element that need to replace. The array is cycle, with index [1..n] (inclusive), so next is increase by one or restart to 1 at next == n+1 every loop

from typing import List


class Heap:
    def getChild(self, x):
        res = []
        if x*2+1 <= self.size:
            res.append(x*2+1)
        if x*2 <= self.size:
            res.append(x*2)
        return res

    def getParrent(x):
        return x // 2

    def __init__(self, arr):
        self.heap = [-1] + arr
        self.size = len(arr)
        self.pos = list(range(self.size + 1))
        self.revertPos = list(range(self.size + 1))
        self.next = 1

        for i in range(1, self.size+1):
            self.update(i)

        for i in range(1, self.size+1):
            self.revertPos[self.pos[i]] = i

    def update(self, x):
        if x == 1:
            return
        px = Heap.getParrent(x)
        if self.heap[x] > self.heap[px]:
            self.heap[x], self.heap[px] = self.heap[px], self.heap[x]
            self.pos[x], self.pos[px] = self.pos[px], self.pos[x]
            self.revertPos[self.pos[x]], self.revertPos[self.pos[px]
                                                        ] = self.revertPos[self.pos[px]], self.revertPos[self.pos[x]]

            self.update(px)

    def downgrade(self, x):
        cx_arr = self.getChild(x)
        if len(cx_arr) == 2 and self.heap[cx_arr[1]] > self.heap[cx_arr[0]]:
            cx_arr.pop(0)
        for cx in cx_arr:
            if self.heap[x] < self.heap[cx]:
                self.heap[x], self.heap[cx] = self.heap[cx], self.heap[x]
                self.pos[x], self.pos[cx] = self.pos[cx], self.pos[x]
                self.revertPos[self.pos[x]], self.revertPos[self.pos[cx]
                                                            ] = self.revertPos[self.pos[cx]], self.revertPos[self.pos[x]]
                self.downgrade(cx)
                break

    def incNext(self):
        if self.next >= self.size:
            self.next = 1
        else:
            self.next += 1

    def replace(self, v):
        pos = self.revertPos[self.next]
        self.incNext()
        old = self.heap[pos]
        self.heap[pos] = v
        if old < v:
            self.update(pos)
        else:
            self.downgrade(pos)


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = Heap(nums[:k])
        res = [heap.heap[1]]

        for i in nums[k:]:
            heap.replace(i)
            res.append(heap.heap[1])

        return res

Last update : October 13, 2023
Created : August 16, 2023