MediumArrayHash TableUnion FindUpdated Sep 2026

128. Longest Consecutive Sequence

Asked at Google, Amazon, Apple, Microsoft and 3 more

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

7

Problem

You get an array of integers that is not sorted. Return the length of the longest run of consecutive integers that you can build from the values in the array.

The values do not need to sit next to each other in the array. Only their values matter. For example, [100,4,200,1,3,2] contains the values 1, 2, 3 and 4, so the answer is 4 even though they are scattered.

Duplicates do not help — a value can be used only once, so [1,0,1,2] gives the run 0, 1, 2 of length 3. Your algorithm must run in O(n) time, so sorting is not allowed.

Scattered values, one hidden run

nums1004200132012345The green cells are the run 1, 2, 3, 4 — they are notnext to each other in the array
The array is unsorted, but the values 1, 2, 3, 4 are all there, so the answer is 4.

Constraints

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

Examples

Example 1
Inputnums = [100,4,200,1,3,2]
Output4
WhyThe values 1, 2, 3, 4 form a consecutive run. No longer run exists, so the answer is 4.
Example 2
Inputnums = [0,3,7,2,5,8,4,6,0,1]
Output9
WhyThe values 0 through 8 are all present, giving a run of 9 numbers. The extra 0 is a duplicate and adds nothing.
Example 3
Inputnums = [1,0,1,2]
Output3
WhyThe values 0, 1, 2 form a run of length 3. The second 1 is a repeat, so it cannot extend the run.

Asked At

7 companies
CompanyDifficulty
GoogleMediumView all Google questions →
AmazonMediumView all Amazon questions →
AppleMediumView all Apple questions →
MicrosoftMediumView all Microsoft questions →
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

Brute force: sort the array, then scan for consecutive runs. O(n log n). The interviewer wants O(n).

2

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.

3

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).

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).

Only count from a sequence start

set1004200132num = 1: 0 is not in the set, so 1 is a start — count2, 3, 4 and stop at 5set1004200132num = 4, 3, 2: each has num-1 in the set, so they areskipped in O(1)if num-1 not in set: length = 1 while num+length in set: length++best = max(best, length)
A number starts a run only when num-1 is missing. Then we walk upward through the set.
ComplexityTime O(n)Space O(n)Building the hash set costs O(n) time and space, and each number is looked up at most twice, so the total stays linear.

What Trips People Up in Real Interviews

1

Sorting first. That's O(n log n) and works, but the interviewer wants O(n) using a hash set.

2

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.

3

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.

4

Forgetting that duplicates should be ignored. Use a set, not a list. Duplicates don't extend the sequence.

5

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

O(n) time
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 best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Consecutive Sequence?

Longest Consecutive Sequence is asked at Google, Amazon, Apple, Microsoft, Oracle, Walmart, NVIDIA. 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.