Longest Consecutive Sequence: A Set-Based Approach

The "Longest Consecutive Sequence" problem is an intriguing challenge that involves finding the length of the longest sequence of consecutive numbers in an unsorted array.

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. The sequence must be strictly consecutive, and the numbers in the sequence can appear in any order in the array.

Example

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

Set-Based Solution

function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let longestStreak = 0;

  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentStreak = 1;

      while (numSet.has(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }

      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}

Breaking Down the Solution

• Create a Set: Convert the array into a set to allow for O(1) lookups and to eliminate duplicates.
• Iterate Through the Set: For each number, check if it's the start of a sequence (i.e., num - 1 is not in the set).
• Expand the Sequence: If it's the start, count the length of the consecutive sequence by continuously checking the presence of the next numbers in the set.
• Track the Longest Sequence: Update the longest sequence length found so far.

Time Complexity

1. Creating the Set: Converting the array into a set has a time complexity of O(N), where N is the number of elements in the array. This is because each element is added to the set once.

2. Iterating Through the Set: The main loop iterates through each element of the set. For each element, it checks whether it is the start of a new sequence (i.e., whether num - 1 is not in the set).

3. Finding Consecutive Numbers: For each starting element of a sequence, the algorithm potentially iterates through the consecutive numbers following it. In the worst case, if there is a long consecutive sequence, this could seem like an additional nested loop. However, each element in the array is visited at most twice in these operations: once when it's checked as a potential start of a sequence, and once when it's counted as part of an existing sequence.

   The key insight is that, although there's a nested loop, each element from the original array contributes to the longest streak only once. This means the total number of operations is still proportional to N.

Putting it all together, the worst-case time complexity is O(N).

Space Complexity

The space complexity is primarily determined by the set used to store the elements of the array. Since the set contains every distinct element from the original array, the space complexity is O(N).

Summary

The set-based approach for the "Longest Consecutive Sequence" problem is efficient with a linear time complexity of O(N) and a linear space complexity of O(N), making it a suitable solution for large arrays.

Conclusion

The Longest Consecutive Sequence problem is an excellent application of sets in algorithms, demonstrating their utility in efficiently solving problems that involve uniqueness and ordering. It emphasizes the importance of choosing the right data structure for optimal performance in solving complex problems.