TLE for union-find solution


  • 0
    L

    This is my union-find solution. I do compression on the findRoot() method, so I think the time complexity should be in O(n), but it got TLE. Anyone can help to improve the performance?

    public class Solution {
        public int longestConsecutive(int[] nums) {
            Map<Integer, Integer> roots = new HashMap<Integer, Integer>();
            
            for(int i = 0; i < nums.length; i++) {
                roots.put(nums[i], nums[i]);
            }
            
            for(int item : roots.keySet()) {
                if(roots.containsKey(item + 1)) {
                    roots.put(item, item + 1);
                }
            }
            
            for(int item : roots.keySet()) {
                findRoot(roots, item);
            }
            
            // aggregate by root
            Map<Integer, Integer> unions = new HashMap<Integer, Integer>();
            int max = -1;
            for(int item : roots.keySet()) {
                int unionId = roots.get(item);
                if(!unions.containsKey(unionId)) {
                    unions.put(unionId, 1);
                } else {
                    unions.put(unionId, unions.get(unionId) + 1);
                }
                max = Math.max(max, unions.get(unionId));
            }
            
            return max;
        }
        
        private void findRoot(Map<Integer, Integer> roots, int item) {
            int cur = item;
            while(item != roots.get(item)) {
                item = roots.get(item);
            }
            roots.put(cur, item);
        }
    }
    

Log in to reply
 

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