TIC
The Interns Company

Longest Consecutive Sequence

MediumAcceptance: 48.2%
ArrayHash TableUnion Find

Problem Statement

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.

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Input Format:

  • An unsorted array of integers nums

Output Format:

  • The length of the longest consecutive elements sequence

Examples:

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

Explanation:

The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Therefore its length is 9.

Example 3:

Input:

nums = []

Output:

0

Explanation:

The array is empty, so the length of the longest consecutive sequence is 0.

Solutions

Hash Set Approach

Time: O(n)
Space: O(n)

Use a hash set to efficiently check for the presence of consecutive elements.

Union Find Approach

Time: O(n)
Space: O(n)

Use a Union Find data structure to group consecutive elements and keep track of the size of each group.

Sorting Approach

Time: O(n log n) due to sorting
Space: O(1) or O(n) depending on the sorting algorithm

Sort the array first, then count consecutive elements. This approach is simpler but does not meet the O(n) time requirement.

Algorithm Walkthrough

Example input: nums = [100,4,200,1,3,2]

Step-by-step execution:

  1. Create a set: {1, 2, 3, 4, 100, 200}
  2. Iterate through the set:
  3. Check 1: 1-1=0 is not in the set, so 1 is the start of a sequence
  4. Count consecutive numbers: 1, 2, 3, 4 (length = 4)
  5. Check 2: 2-1=1 is in the set, not the start of a sequence, skip
  6. Check 3: 3-1=2 is in the set, not the start of a sequence, skip
  7. Check 4: 4-1=3 is in the set, not the start of a sequence, skip
  8. Check 100: 100-1=99 is not in the set, so 100 is the start of a sequence
  9. Count consecutive numbers: 100 (length = 1)
  10. Check 200: 200-1=199 is not in the set, so 200 is the start of a sequence
  11. Count consecutive numbers: 200 (length = 1)
  12. Max sequence length = 4

Hints

Hint 1
Use a hash set to efficiently check if a number exists in the array.
Hint 2
For each number, check if it's the start of a sequence by looking for the presence of the previous number.
Hint 3
If it is the start of a sequence, keep counting consecutive numbers until the sequence ends.

Video Tutorial

Longest Consecutive Sequence - Hash Set Approach

YouTube•Learn the Longest Consecutive Sequence solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the consecutive sequences found in the array.

Key visualization elements:

  • current number
  • current sequence
  • longest sequence

Asked By

GoogleFacebookMicrosoftAmazonAppleAirbnbBloomberg

Implementation Notes

This problem has a clever O(n) solution that uses a hash set to avoid sorting while still efficiently determining the longest consecutive sequence.