{x}
blog image

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

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.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Solution Explanation for Longest Consecutive Sequence

The problem asks to find the length of the longest consecutive sequence of numbers within an unsorted array. The solution needs to be optimized to O(n) time complexity.

Two approaches are presented using hash tables (sets in Python and some other languages):

Approach 1: Hash Table with Length Tracking

This approach uses two hash tables (or sets and maps):

  1. s: A set to store all unique numbers from the input array. This allows for O(1) lookup time.
  2. d: A map to store the length of the longest consecutive sequence ending at each number.

The algorithm iterates through each number x in the input array:

  • It initializes y to x.
  • It enters a while loop that continues as long as y is found in s. Inside this loop:
    • It removes y from s.
    • It increments y. This effectively finds the end of the consecutive sequence starting from x.
  • After the loop, d[x] (the length of the sequence ending at x) is calculated as d[y] + y - x. The d[y] term handles cases where the sequence continues beyond y (from a previous iteration).
  • Finally, the ans variable (tracking the maximum sequence length) is updated.

Time Complexity Analysis: The algorithm iterates through the input array once (O(n)). The while loop inside has a total number of iterations equal to the total length of all consecutive sequences. Since each element is only involved in one consecutive sequence, the total number of loop iterations is O(n). Therefore the overall time complexity is O(n).

Space Complexity Analysis: The space complexity is O(n) because we use a set s and a map d, both of which can store up to n elements in the worst case (all numbers are unique and form a single long sequence).

Approach 2: Hash Table Optimization

This approach improves upon the first by avoiding the second hash table (d). It utilizes only a set s and relies on the observation that only the start of a consecutive sequence needs to be considered.

The algorithm iterates through the set s:

  • It checks if x - 1 is in s. If it is, x is not the start of a new consecutive sequence, so it's skipped.
  • If x - 1 is not in s, it means x is the start of a consecutive sequence. A while loop is used to find the end of this sequence (similar to Approach 1).
  • The length of the current sequence (y - x) is calculated and ans is updated accordingly.

Time Complexity Analysis: Similar to Approach 1, the time complexity is O(n). Each element is visited at most once, and the total number of iterations in the while loop is bounded by n.

Space Complexity Analysis: The space complexity is O(n) due to the use of the set s.

Both approaches achieve the required O(n) time complexity, but Approach 2 is slightly more efficient in terms of space because it avoids the second hash table. The choice between them depends on coding style preference and potential trade-offs between space and readability. Approach 2 is generally preferred for its conciseness.