Why does my nlgn + klgn method using PriorityQueue TLE?


  • 0
    Y

    class Solution {

    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for (int i = 0; i < nums.length - 1; i++) {
            pq.offer(new Pair(i, i + 1, nums[i + 1] - nums[i]));
        }
        for (int i = 0; i < k - 1; i++) {
            Pair curr = pq.poll();
            if (curr.secondIdx < nums.length - 1) {
                pq.offer(new Pair(curr.firstIdx, curr.secondIdx + 1, nums[curr.secondIdx + 1] - nums[curr.firstIdx]));
            }
        }
        return pq.poll().value;
    }
    
    static class Pair implements Comparable<Pair> {
        int firstIdx;
        int secondIdx;
        int value;
        
        Pair(int firstIdx, int secondIdx, int value) {
            this.firstIdx = firstIdx;
            this.secondIdx = secondIdx;
            this.value = value;
        }
        
        @Override
        public int compareTo(Pair that) {
            
            return this.value < that.value ? -1 : 1;
        }
    }
    

    }


  • 0
    S

    Hmm, I have taken the same approach and running into TLE. @YunxiLiu Did you have any luck here?


  • 0
    S

  • 0
    Y

    @simonzhu91 Thanks!! It is right.


Log in to reply
 

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