Longest Consecutive Sequence

Problem: Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 

Example:

Input: nums = [10,4,20,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Approach: A simple obvious approach could be sort the array but this will take O(nlogn) time. It can be solved in O(n) using hash. Here are the steps -

1. Hash all the numbers in the array.
2. For each number in array, do the following:
1. Current Length is 1 (element itself)
2. If current number - 1 is not in hash then current number could be the starting number of sequence.
3. Check for current number + 1 in hash and keep increasing current length and number by 1 till the current number is not found in hash.
4. Assign result to max of result and current length.

Implementation in C#:

    public int LongestConsecutive(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        var numSet = new HashSet<int>(nums);

        int maxLength = 1;

        foreach(int num in nums)

        {

            if (!numSet.Contains(num - 1))

            {

                int currLength = 1;

                int temp = num;

                while (numSet.Contains(temp + 1))

                {

                    ++temp;

                    ++currLength;

                }

                maxLength = Math.Max(currLength, maxLength);

            }

        }

        return maxLength;

    }

Complexity: O(n)