A C# O(NLogN) SortedSet & A O(N) HashSet Solution


  • 0
    L

    C# SortedSet O(nLogn)

    public int LongestConsecutive(int[] nums) {
        SortedSet<int> ss = new SortedSet<int>(nums);
        int maxSeq = 1, curSeq = 1, lastNum = int.MaxValue;
        foreach(var num in ss){
            if(lastNum != int.MaxValue && num == lastNum + 1) curSeq++;
            else curSeq = 1;
            maxSeq = Math.Max(maxSeq, curSeq);
            lastNum = num;
        }
        return maxSeq;
    }
    

    C# HashSet O(N)

    public int LongestConsecutive(int[] nums) {
        HashSet<int> hs = new HashSet<int>(nums);
        int maxSeq = 0;
        for(int i = 0, curSeq = 1; i < nums.Length; i++, curSeq = 1){
            hs.Remove(nums[i]);
            for(int j = 1; nums[i] <= int.MaxValue - j && hs.Contains(nums[i] + j); j++){
                hs.Remove(nums[i] + j);
                curSeq++;
            }
            for(int j = 1; nums[i] >= int.MinValue + j && hs.Contains(nums[i] - j); j++){
                hs.Remove(nums[i] - j);
                curSeq++;
            }
            maxSeq = Math.Max(maxSeq, curSeq);
        }
        return maxSeq;
    }

  • 0

    The problem says "Your algorithm should run in O(n) complexity" and if I'm not mistaken, that constructor is an O(n log n) operation.


  • 0
    L

    Thanks for pointing it out, ManueIP. I fixed it by using Hashset now.

    public int LongestConsecutive(int[] nums) {
        HashSet<int> hs = new HashSet<int>();
        int maxSeq = 0;
        for(int i = 0; i < nums.Length; i++) hs.Add(nums[i]);
        for(int i = 0, curSeq = 1; i < nums.Length; i++, curSeq = 1){
            hs.Remove(nums[i]);
            for(int j = 1; nums[i] <= int.MaxValue - j && hs.Contains(nums[i] + j); j++){
                hs.Remove(nums[i] + j);
                curSeq++;
            }
            for(int j = 1; nums[i] >= int.MinValue + j && hs.Contains(nums[i] - j); j++){
                hs.Remove(nums[i] - j);
                curSeq++;
            }
            maxSeq = Math.Max(maxSeq, curSeq);
        }
        return maxSeq;
    }

Log in to reply
 

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