Leetcode discuss: 128. Longest Consecutive Sequence | Downvote -1 -> Code review

July 11, 2022

Here is the link. 

C# | Quick learner | Using HashSet | 2022 July 11

May 29, 2020

I learned the optimal time complexity O(N) algorithm and like to share my practice. The idea is to avoid using sorting algorithm, instead apply search using HashSet, and check if any number is the smallest number in a consecutive sequence first, and then calculate length accordingly.

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

Two ideas | Two sides -> One side | Do not remove a node from a HashSet | TLE problem
I spent 30 minutes to review my original submission, and then analyzed the code, and then learned that there are three issues to address. So I learn one optimal soution first.

1. Next, go over each number in Hashset, apply two while loop to search next bigger one consecutively, next smaller one consecutively as well.
2. Step 1 is a working idea, but bigger or smaller is the same idea. A better and simpler idea is to find it is smallest number in a consecutive sequence, and only work on smallest number.
3. Play with different ideas, and I learned that the idea in step 2 is the best one.

Time complexity: O(N), N is length of the array

One downvote | Code review | a better idea
I spent 30 minutes to review my old discuss post with one down vote. And I learned to write a working solution and please give me upvote here! Thanks!

Solution 1: Using HashSet | One search | avoid HashSet.Remove | No TLE
The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _128_long_consecutive
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = LongestConsecutive(new int[] { 1, 2, 3, 4, 100, 200 });
            Debug.Assert(result == 4); 
        }

        /// <summary>         
        /// Learn a lesson - TLE - Do not remove a node from HashSet
        /// 
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static int LongestConsecutive(int[] numbers)
        {
            var set = new HashSet<int>(numbers);

            int max = 0;
            foreach (var number in numbers)
            {
                // Tip:
                // Learn from https://leetcode.com/problems/longest-consecutive-sequence/discuss/1256456/C-solution
                // always work on smallest number in a consecutive sequence - avoid redudant checking 
                if (!set.Contains(number - 1))
                {
                    int start = number;
                    int length = 1;
                    while (set.Contains(++start))
                    {
                        length++;
                    }

                    max = Math.Max(max, length);
                }
            }

            return max;  
        }  
    }
}

To document my learning experience, I also share the following C# code with TLE error. I also encourage myself to think more carefully, and come out optimal solution.

The following C# code failed, TLE error on 70/72 test case.

Solution 2: TLE error on 70/72 test case

public class Solution {
    public int LongestConsecutive(int[] nums) {
       var set = new HashSet<int>(nums); 
        
        int maxLength = 0;
         while (set.Count > 0)
         {
            var first = set.First();
            var last = first;
             
            while(set.Contains(first - 1))
            {
                first -= 1; 
                set.Remove(first);                               
            }

            set.Remove(last);
             
            while(set.Contains(last + 1))
            {   
                last = last + 1;
                set.Remove(last);                
            }            
            
            maxLength = Math.Max(maxLength, last - first + 1);
         }            
         
         return maxLength; 
    }
}