Longest Consecutive Sequence in Array

The LongestConsecutive method finds the length of the longest consecutive sequence in an array of integers. Let’s break down the code and understand its functionality, time complexity, and potential optimizations.

Consider the below arrays.

• Input: nums = [100,6,200,5,7,8]
• Output: 4
• Explanation: The longest consecutive elements sequence is [5, 6, 7, 8]. Therefore, its length is 4.

public int LongestConsecutive(int[] nums)
{
    HashSet<int> set = new HashSet<int>(nums);
    int count = 1;
    foreach (var item in nums)
    {
        if (!set.Contains(item + 1))
        {
            int num = item - 1;
            while (set.Contains(num))
            {
                set.Remove(num);
                num--;
                count = Math.Max(count, item - num);
            }
        }
    }

    return nums.Length > 0 ? count : 0;
}

Code Explanation

1. HashSet Initialization
   • The method starts by creating a HashSet<int> from the input array nums. This allows for O(1) average-time complexity for lookups.
   • HashSet<int> set = new HashSet<int>(nums);
2. Initial Count
   • A variable count is initialized to 1. This will keep track of the length of the longest consecutive sequence found.
   • int count = 1;
3. Iterating Through the Array
   • The method iterates through each element in the array nums.
   • foreach (var item in nums)
4. Checking for Sequence End
   • For each element, it checks if the next element (item + 1) is not in the set. This indicates that the current element might be the end of a consecutive sequence.
   • if (!set.Contains(item + 1))
5. Finding the Start of the Sequence
   • If the current element is the end of a sequence, the method then looks for the start of the sequence by decrementing the element (item - 1) until it finds an element not in the set.
   • int num = item - 1;
   • while (set.Contains(num))
6. Updating the Count
   • During this process, the method updates the count to reflect the length of the sequence.
   • count = Math.Max(count, item - num);
7. Returning the Result
   • Finally, the method returns the length of the longest consecutive sequence found, or 0 if the array is empty.
   • return nums.Length > 0 ? count : 0;

Below is the example with I/P and O/P.

Time Complexity

The time complexity of this method is O(n), where n is the number of elements in the input array. Here’s why