Longest Consecutive Sequence
Asked at Google, Amazon, Apple, Microsoft, Oracle, Walmart
Problem
Given an unsorted array of integers, find the length of the longest consecutive elements sequence in O(n) time. This problem tests whether you can achieve linear time using a hash set.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: sort the array, then scan for consecutive runs. O(n log n). The interviewer wants O(n).
Key insight: only start counting from the beginning of a sequence. If num-1 exists in the set, this num is not a sequence start — skip it. This avoids counting the same sequence multiple times.
Why this is O(n): each element is visited at most twice — once in the outer loop, once in the inner while loop. Elements that are not sequence starts are skipped in O(1).
Visual walkthrough for [100,4,200,1,3,2]:
Set: {100,4,200,1,3,2}
- num=100: 99 not in set → sequence start. Count: 101 (no), 102 (no). Length=1.
- num=4: 3 in set → skip (not a start).
- num=200: 199 not in set → sequence start. Count: 201 (no). Length=1.
- num=1: 0 not in set → sequence start. Count: 2 ✓, 3 ✓, 4 ✓, 5 (no). Length=4.
- num=3: 2 in set → skip.
- num=2: 1 in set → skip.
Result: 4 (sequence 1,2,3,4)
Edge cases: empty array (return 0), all elements the same (return 1), no consecutive elements (return 1).
Optimal Approach
Step 1: Put all numbers in a hash set.
Step 2: For each number in the set:
- If num-1 is in the set, skip (not a sequence start)
- If num-1 is not in the set, this is a sequence start
- Count forward: num+1, num+2, ... while in the set
- Track the maximum length
The hash set gives O(1) lookups. The key insight is that you only count from sequence starts, so each element is processed at most twice.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
Sorting first. That's O(n log n) and works, but the interviewer wants O(n) using a hash set.
Not checking if the current number is the start of a sequence. Only start counting from numbers that have no predecessor (num - 1 not in the set). This avoids recounting subsequences.
Confusing "consecutive" with "sorted." Consecutive means each number is exactly 1 more than the previous. [1, 2, 4] has consecutive sequences of length 2 and 1, not 3.
Forgetting that duplicates should be ignored. Use a set, not a list. Duplicates don't extend the sequence.
Not converting the input to a set. Checking if num-1 exists in a list is O(n), making the whole algorithm O(n²). Convert to a set first for O(1) lookups.
Solution Code
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for num in num_set:
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
best = max(best, length)
return bestFrequently Asked Questions
What is the Longest Consecutive Sequence problem?
Given an unsorted array of integers, find the length of the longest consecutive elements sequence in `O(n)` time. This problem tests whether you can achieve linear time using a `hash set`.
How do you solve Longest Consecutive Sequence?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Consecutive Sequence?
Longest Consecutive Sequence is asked at Google, Amazon, Apple, Microsoft, Oracle, Walmart. It is a medium difficulty problem.
What are common mistakes on Longest Consecutive Sequence?
- Sorting first. That's `O(n log n)` and works, but the interviewer wants `O(n)` using a `hash set`.
- Not checking if the current number is the start of a sequence. Only start counting from numbers that have no predecessor (num - 1 not in the set). This avoids recounting subsequences.
- Confusing "consecutive" with "sorted." Consecutive means each number is exactly 1 more than the previous. `[1, 2, 4]` has consecutive sequences of length 2 and 1, not 3.
- Forgetting that duplicates should be ignored. Use a set, not a list. Duplicates don't extend the sequence.
- Not converting the input to a set. Checking if num-1 exists in a list is `O(n)`, making the whole algorithm `O(n²)`. Convert to a set first for `O(1)` lookups.