Leetcode discuss: 128. Longest Consecutive Sequence

Here is the post.

C# Data structure SortedSet<int> practice in 2018

May 29 2020
It is hard level algorithm. I like to share my practice in 2018. C# SortedSet is designed using advanced data structure called a self-balancing red-black tree. I like to chosen SortedSet to solve the longest consecutive sequence problem.

Test case study
Given an input array [100, 4, 200, 1, 3, 2], how to solve it using time complexity O(NlogN), and also space complexity O(N), whereas N is the total number of nodes in the array.

First, save the integer array into C# SortedSet, denoted as sortedSet. So sortedSet is in sorted order from 1, 2, 3, 4, 100, 200, but it should be in the structure of tree; Next, go over each number in sortedSet, if two neighbor elements are not in difference of 1, then a new consecutive sequence starts.

More detail, start from value 1, iterate 2, 3, 4, length is 4. Next one is 100, so a new consecutive sequence starts and ends as well, next one is 200. So the longest length is 4.

C# SortedSet warmup

I also have to learn how C# SortedSet is designed. Here is the reference I look into on stackoverflow.
It is implemented using a self-balancing red-black tree that gives a performance complexity of O(log n) for insert, delete, and lookup. It is used to keep the elements in sorted order, to get the subset of elements in a particular range, or to get the Min or Max element of the set.

public class Solution {
    public int LongestConsecutive(int[] nums) {
         if (nums == null || nums.Length == 0)
            {
                return 0; 
            }

            var binarySearchTree = new SortedSet<int>(nums);

            int maxSequence     = 1;
            int currentSequence = 1;

            int lastNumber = int.MaxValue;

            foreach (var number in binarySearchTree)
            {
                if (lastNumber != int.MaxValue && number == lastNumber + 1)
                {
                    currentSequence++;
                }
                else
                {
                    currentSequence = 1;
                }

                maxSequence     = Math.Max(maxSequence, currentSequence);
                lastNumber = number;
            }

            return maxSequence;
    }
}