Priority Queue Solution


  • 0
    W

    I just thought of putting the values in a heap and then return the second smallest.

    class Solution {
        public int findSecondMinimumValue(TreeNode root) {
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
            
            add(root,pq);
            
            if(pq.isEmpty() || pq.size()<3) return -1;
            
            int temp = pq.poll();
            
            while(!pq.isEmpty()){
                
                if(temp!=pq.peek()) return pq.peek();
                pq.poll();
            }
            
            return -1;
            
        }
        
        public static void add(TreeNode root, PriorityQueue<Integer> pq){
            if(root==null) return;
            pq.add(root.val);
            add(root.left,pq);
            add(root.right,pq);
            return;
        }
    }
    

    Improvements/feedback appreciated!


  • 0
    A

    Instead of Priority Queue you could use TreeSet instead.

    public int findSecondMinimumValue(TreeNode root) {
            TreeSet<Integer> ts = new TreeSet<Integer>();
            add(root, ts);
            ts.pollFirst();
            if(!ts.isEmpty()) return ts.first(); else return -1;
        }

  • 0
    W
    This post is deleted!

  • 0
    W

    @aayushgarg Yes. I thought of treeset as well.
    But adding to it also costs logn per entry, are there any time complexity improvements?


  • 0
    A

    @waltwhitman Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element. Both TreeSet and Priority queue provides O(log(N)) complexity for adding, removing and searching elements.

    Set will not store multiple duplicate elements in memory, thus improving space complexity.


  • 0
    W

    @aayushgarg Yes!!
    The only gain is of space complexity otherwise time complexity remains same.
    Thanks!


Log in to reply
 

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