I don’t think you need to keep track of the number’s index in the queue itself since you only need to start sliding the window once you’ve checked at least k numbers. In other words, you only need to start shifting the window inside the i >= k - 1 check. You also don’t need it to keep track of what to dequeue when shifting the window, even if there are repeats, since you can derive what number needs to be dequeued from checking if the first number in the queue matches nums[i - k + 1]. I like this approach better.
const queue = [];
const res = [];
for (let i = 0; i < nums.length; i++) {
// Pop last num in queue while it's less than new num to be added
while (queue.length > 0 && queue[queue.length - 1] < nums[i]) {
queue.pop();
}
queue.push(nums[i]);
// If we've checked at least k elements, start pushing to res
if (i >= k - 1) {
// Only push largest num in queue which will always be the first num.
res.push(queue[0]);
// Move left part of window over by 1.
// Index to be dequeued will be i - k + 1.
// If queue[0] matches the num to be dequeued, dequeue it.
const dequeueIndex = i - k + 1;
if (queue[0] === nums[i - k + 1]) {
queue.shift();
}
}
}
return res;
My Solution, without stacking the indices,
def sliding_window_maximum(nums: List[int], k: int) → List[int]:
res = []
stack = []
for i in range(len(nums)):
while stack and nums[i] > stack[-1]:
stack.pop()
stack.append(nums[i])
# make sure i-k is valid, and pop it out from the stack/deque at the left when equals to nums[i-k]
if i>=k and stack[0] == nums[i-k]:
stack.pop(0)
if i >= k-1:
res.append(stack[0])
return res
Repost because of the format issue
from typing import List
def sliding_window_maximum(nums: List[int], k: int) → List[int]:
res = []
stack = []
for i in range(len(nums)):
while stack and nums[i] > stack[-1]:
stack.pop()
stack.append(nums[i])
# make sure i-k is valid, and pop it out from the stack/deque at the left when equals to nums[i-k]
if i>=k and stack[0] == nums[i-k]:
stack.pop(0)
if i >= k-1:
res.append(stack[0])
return res
Another solution that uses Priority Queue
public static List slidingWindowMaximum(List nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
List<Integer> result = new ArrayList<>();
for(int i = 0; i < nums.size(); i++)
{
pq.add(nums.get(i)); // add an item to the PriorityQueue
if (pq.size() == k + 1) // clean the item after when the window shifts
pq.remove(nums.get(i - k));
if (pq.size() == k)
result.add(pq.peek()); // add the item from the top of the PriorityQueue
}
return result;
}
Why haven’t you suggested Heaps as a possible solution ? Since you have a huge section on Heaps on algo monster compared to self-balancing BSTs.
Can’t we solve the problem using a max heap - we store indices in the heap rather than the values. After we initialize the first window, we could simply delete/remove the left ptr index, add the right ptr index and peek() to find max for each window. Since Heaps are complete BTs , I am assuming all operations will be O(1) or O(logk) giving us - O(Nlogk)
You are right! Heap would be the more natural choice than BST since we only need max here. I will update the article. The time complexity will be O(nlog(k)), a little bit worse than mono stack.
I didn’t get how to use Heap here, because if we build Heap using indexes, how can we find the maximum value? Or if we use values, how can we remove the leftmost index from Heap?
The space complexity was mentioned as O(N) for the deque solution. However, considering that the deque size is limited by the window size ‘k’ and not the total number of elements ‘N’, shouldn’t the space complexity be O(k) instead? I would appreciate your thoughts on this, as I want to ensure I have a correct understanding of the concept.