# Learning Priority Queues. Wrote an accepted code. Help me figure out complexity.

• '''
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {

``````    if(nums.length == 0)
return new int[0];

int[] ans = new int[nums.length - k + 1];
int t = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
int n = nums.length;

for(int i = 0; i < k; i++) {
queue.add(nums[i]);
}
ans[t++] = queue.peek();

int i = k;
while(i < n) {
queue.remove(nums[i - k]);
queue.add(nums[i]);
ans[t++] = queue.peek();
i++;
}
return ans;
}
``````

}

'''

Can someone help me figure out the time complexity of this accepted solution ? I have just started learning priority queues.

Thanks!!

• @coder18694 The space complexity is O(k) and the time complexity is O(nlogk).

O(nlogk) -> adding n elements in the priority queue where it will try sorting with the complexity of O(logk).

While your solution was accepted, it won't work with duplicates. I just posted a solution that works on an IDE but not here so not sure what is going on.

• I went through all cases when moving the window to the right side by one. Actually, I could not find any problem with the case of duplicates. Regardless duplicates, the `remove` step removes the `i-k` value from the queue, so the maximum is indeed correctly maintained, as far as I can see.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.