Simple C# solution with Weighted Union Find


  • 0
    Z

    Instead of using an integer array as the backing structure in UF and a separate hashmap to keep track of what numbers were processed so far, I used two dictionaries to implement union find and also to keep track of sizes & what is added so far.

    public class Solution {
        // Weighted union find
        Dictionary<int, int> id = new Dictionary<int, int>();
        Dictionary<int, int> size = new Dictionary<int, int>();
        int maxSize = 1; // Max size seen so far
        
        public int LongestConsecutive(int[] nums) {
            if (nums.Length < 2) return nums.Length;
            
            foreach (int p in nums) {
                Add(p);
                if (id.ContainsKey(p - 1)) Union(p, p - 1);
                if (id.ContainsKey(p + 1)) Union(p, p + 1);
            }
            
            return maxSize;
        }
        
        public void Add(int p) {
            if (!id.ContainsKey(p)) {
                id[p] = p;
                size[p] = 1;
            }
        }
        
        public int Find(int p) {
            while (p != id[p]) {
                id[p] = id[id[p]]; // Path compression
                p = id[p];
            }
            return p;
        }
        
        public void Union(int p, int q) {
            int id1 = Find(p);
            int id2 = Find(q);
            if (id1 == id2) return;
            
            if (size[id1] > size[id2]) {
                id[id2] = id1;
                size[id1] += size[id2];
                maxSize = Math.Max(maxSize, size[id1]);
            }
            else {
                id[id1] = id2;
                size[id2] += size[id1];
                maxSize = Math.Max(maxSize, size[id2]);
            }
        }
    }
    

Log in to reply
 

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