My O(N) union-find solution


  • 1
    J

    Use the path compression weighted union find algorithm. See Algorithms 4th edition for the detailed description.

    public class Solution {
    public int LongestConsecutive(int[] nums) {
        UnionFind uf = new UnionFind(nums.Length);
        
        var dict = new Dictionary<int, int>(); // nums[i] -> i
        
        for(int i = 0; i < nums.Length; i++) {
            if(dict.ContainsKey(nums[i])) {
                continue;
            } else {
                dict.Add(nums[i], i);
                
                if(dict.ContainsKey(nums[i] - 1)) {
                    uf.Union(i, dict[nums[i] - 1]);
                }
                
                if(dict.ContainsKey(nums[i] + 1)) {
                    uf.Union(i, dict[nums[i] + 1]);
                }
            }
        }
        
        return uf.MaxSize;
    }
    
    private class UnionFind
    {
        private int[] parent;
        private int[] size;
        
        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            
            for(int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            MaxSize = 1;
        }
        
        public int MaxSize { get; private set; }
        
        public void Union(int p, int q) {
            int rootP = Find(p);
            int rootQ = Find(q);
            
            if(rootP == rootQ) return;
            if(size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
                MaxSize = Math.Max(MaxSize, size[rootQ]);
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
                MaxSize = Math.Max(MaxSize, size[rootP]);
            }
        }
        
        private int Find(int p) {
            int root = p;
            while(parent[root] != root) {
                root = parent[root];
            }
            
            while(parent[p] != root) {
                int newP = parent[p];
                parent[p] = root;
                p = newP;
            }
            
            return root;
        }
    }
    

    }


  • 0

    I don't see the O(N). Wikipedia mentions amortized O(α(N)) per operation. Is it because it's a special case of only uniting neighbors (in the row of numbers)?


  • 0
    J

    Sorry, my bad. It is not O(N).


  • 0
    B

    U can make some optimization to the "Find()" to make it O(1). Then the total amortized complexity should be O(N).
    The Union() and Find() are both O(1).
    private in Find(int p) {
    if (p != parent[p])
    parent[p] = Find(parent[p]);
    return parent[p];
    }


  • 0
    B

    U can make some optimization to the "Find()" to make it O(1). Then the total amortized complexity should be O(N).
    The Union() and Find() are both O(1).

    private in Find(int p) {
    if (p != parent[p]) 
        parent[p] = Find(parent[p]);
    return parent[p];
    }
    

  • 0

    @birdyhuang Same question for you then: I don't see the O(N). Wikipedia mentions amortized O(α(N)) per operation. Is it because it's a special case of only uniting neighbors (in the row of numbers)?


  • 0

    That's the exact same complexity as johnsonlu's original. And as I said in the comments above, I doubt the amortized O(1). (And it's definitely not "O(1)" (without "amortized")).


  • 0
    B

    "the amortized running time per operation is effectively a small constant." from the link you provided. If each operation is a constant, can we just take it O(1)? Then why it is not O(N)?


  • 0

    Yes, "effectively", but not really. That's still a difference. The way it is written there (with all the context) is ok, but I think one shouldn't just say "O(1)".


  • 0
    This post is deleted!

  • 0

    And like I said, we do have a special case here, and I could actually imagine it being real amortized O(1) due to that. I honestly don't know and can't rule it out. So even for someone knowing about the "effectively" amortized O(1) it's not clear what you mean.


Log in to reply
 

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