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


  • 0
    C

    '''
    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!!


  • 0
    L

    @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.


  • 0
    A

    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.


Log in to reply
 

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