Accepted C#, O(N) time & O(N) space, Undirected Cyclic Graph Solution


  • 1
    H

    Hi All,

    In my approach I created an undirected cyclic Graph where the connected components represent consecutive sequences.

    I welcome constructive criticism.

    public class Solution 
    {
        public int LongestConsecutive(int[] num) 
        {
    
            var d = new Dictionary<int, Bucket>();
            
            for (var i = 0; i < num.Length; ++i)
            {
                Bucket p;
                Bucket n;
                Bucket c;
                
                d.TryGetValue(num[i] - 1, out p);
                d.TryGetValue(num[i] + 1, out n);
                
                if (!d.TryGetValue(num[i], out c))
                {
                    c = new Bucket();
                    d.Add(num[i], c);
                }
                    
                if (n != null)
                {
                    c.Neighbours.Add(n);
                    n.Neighbours.Add(c);
                }
                
                if (p != null)
                {
                    c.Neighbours.Add(p);
                    p.Neighbours.Add(c);
                }
            }
            
            var visited = new Dictionary<Bucket, bool>();
            var maxSequenceCount = 0;
            var q = new Queue<Bucket>();
            
            foreach (var bucket in d.Values)
            {
                q.Enqueue(bucket);
                
                var setSize = 0;
                
                while (q.Count > 0)
                {
                    var b = q.Peek();
                    q.Dequeue();
                    bool beenThere = false;
                    
                    if (visited.TryGetValue(b, out beenThere) && beenThere)
                        continue;
                        
                    visited[b] = true;
                    
                    foreach (var n in b.Neighbours)
                    {
                        beenThere = false;
                    
                        if (visited.TryGetValue(n, out beenThere) && beenThere)
                            continue;
                        
                        q.Enqueue(n);
                    }
                    
                    ++setSize;
                }
                
                maxSequenceCount = Math.Max(maxSequenceCount, setSize);
            }
            
            return maxSequenceCount;
        }
        
        private class Bucket
        {
            public HashSet<Bucket> Neighbours = new HashSet<Bucket>();
        }
    }
    

  • 1
    X

    Absolutely nice idea. But the code is kind of long. Not sure if being able to finish this in an interview.


Log in to reply
 

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