Loading…

mediumArraysLC #128Frequently asked

Longest Consecutive Sequence

Q: How do you solve Longest Consecutive Sequence using the Sort Then Scan approach?

When to use it: The intuitive answer — but it's O(n log n), so flag that it misses the O(n) requirement. Sort the array, then sweep left to right. Keep a `current` run length: if the next element is exactly one more than the previous, extend the run; if it's equal, skip it (duplicate); otherwise reset the run to 1. Track the maximum run seen. **Why mention it.** It's the natural first instinct and is easy to get right. But the problem explicitly asks for O(n), so this is the baseline you improve on with the hash-set method. Time complexity: O(n log n). Space complexity: O(1).

Q: How do you solve Longest Consecutive Sequence using the Hash Set — Start-Only Walk (Optimal) approach?

When to use it: The required O(n) answer. Lead with the 'only start from sequence beginnings' insight. Insert all numbers into a hash set (which also removes duplicates). Then iterate the set; for each value `x`, check whether `x-1` is present. If it is, `x` sits in the middle of some run and we skip it — counting from here would be redundant. If `x-1` is absent, `x` is the smallest element of its run, so we walk upward `x+1, x+2, …` while each is in the set, counting the length, and update the best. **Why it's O(n), not O(n²).** The nested while loop looks dangerous, but it only ever executes for sequence *starts*. A run of length L has exactly one start, and its while loop runs L steps — visiting each of the run's L elements once. Summed over all runs, that's every element visited a constant number of times: O(n) total. Time complexity: O(n). Space complexity: O(n).

LCPractice

Arrays & Hashing · 7 of 83 · 8 min

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.

In plain English

A 'consecutive sequence' is a set of integers that form an unbroken run like 3,4,5,6 — order in the array is irrelevant, only the values matter. We want the length of the longest such run that can be assembled from the array's values.

Examples

Example 1

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Note: The run 1,2,3,4 has length 4.

Example 2

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Note: 0 through 8 form a run of length 9 (the duplicate 0 doesn't matter).

Example 3

Input: nums = []
Output: 0
Note: No elements, no sequence.

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Clarifying questions4First question: Does the sequence have to appear in order in the array?Explore questions

Q1.Does the sequence have to appear in order in the array?
No — only the values matter. [100, 4, 200, 1, 3, 2] yields the run 1,2,3,4 even though they're scattered.
Q2.Are duplicates possible, and do they affect the count?
Yes, duplicates can appear; they don't lengthen a run. Using a set naturally collapses them.
Q3.What should an empty array return?
0 — there's no sequence.
Q4.Is sorting acceptable?
It gives the right answer in O(n log n), but the problem demands O(n), so we use the hash-set method.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the length of the longest run of consecutive integers, in O(n). Dump everything into a hash set, then only start counting a run from a number whose predecessor (x−1) is absent — that number is a sequence start. Walk x, x+1, x+2… while each is in the set. Each number is visited at most twice overall, so it's O(n) despite the nested-looking loops.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can hit O(n) without sorting by using a hash set and the start-of-sequence optimization — and whether you can justify the linear bound despite a while-loop inside a for-loop.

Where candidates slip

Walking a sequence from every element (O(n²)), or sorting and calling it optimal when O(n) was required.

How to stand out

Explain the amortized O(n) argument: the inner while loop only runs for sequence starts, and across all starts it visits each element once.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort Then Scan	`O(n log n)`	`O(1)`	The intuitive answer — but it's O(n log n), so flag that it misses the O(n) requirement.	Read
2	Hash Set — Start-Only Walk (Optimal)Optimal	`O(n)`	`O(n)`	The required O(n) answer. Lead with the 'only start from sequence beginnings' insight.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFor each x in setIs x-1 in the set?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort Then Scan

TimeO(n log n)SpaceO(1)

The intuitive answer — but it's O(n log n), so flag that it misses the O(n) requirement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the numbers were in order, how would you measure the longest unbroken run?

2Hint 2Explore hint

Sort, then scan once counting how long each consecutive run lasts, resetting on gaps.

3Hint 3Explore hint

Skip duplicates while scanning. It works, but sorting costs O(n log n) — not the required O(n).

A · Core idea

Sort the array, then sweep left to right. Keep a current run length: if the next element is exactly one more than the previous, extend the run; if it's equal, skip it (duplicate); otherwise reset the run to 1. Track the maximum run seen.

Why mention it. It's the natural first instinct and is easy to get right. But the problem explicitly asks for O(n), so this is the baseline you improve on with the hash-set method.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [100, 4, 200, 1, 3, 2]

1→2→3→4

each +1, extend run

Statecurrent=4, best=4

Final result4

C · Code with teaching comments

Reference implementation previewpublic int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; Arrays.sort(nums); int best = 1, current = 1; for (int i = 1; i < nums.length; i++) {Explore the full code

solution.javaJava

Sort Then Scan — reference

2 teaching notes

1
public int longestConsecutive(int[] nums) {
2
    if (nums.length == 0) return 0;
3
    Arrays.sort(nums);
4
    int best = 1, current = 1;
5
    for (int i = 1; i < nums.length; i++) {
6
        // Skip duplicates so they don't reset or inflate the run.
7
        if (nums[i] == nums[i - 1]) continue;
8
        // Exactly one more → the run continues.
9
        if (nums[i] == nums[i - 1] + 1) {
10
            current++;
11
        } else {
12
            current = 1;
13
        }
14
        best = Math.max(best, current);
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Sorting makes 'consecutive' a local property (adjacent elements), which is easy to scan — but paying O(n log n) to get locality is exactly the cost the hash-set approach avoids.

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n); the linear scan after is O(n). O(1) extra space if sorting in place.

E · Edge cases and pitfalls3Not handling duplicates — they can falsely reset or break runs.Explore edge cases

Pitfalls

Not handling duplicates — they can falsely reset or break runs.
Returning 0 for a non-empty array because best wasn't seeded to 1.
Claiming O(n) — sorting makes it O(n log n).

03.2

Approach 2 of 2 · Optimal

Hash Set — Start-Only Walk (Optimal)

TimeO(n)SpaceO(n)

The required O(n) answer. Lead with the 'only start from sequence beginnings' insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Put everything in a set for O(1) membership. How do you avoid recounting the same run from different elements?

2Hint 2Explore hint

A number x begins a sequence only if x-1 is NOT in the set. Start counting just from those.

3Hint 3Explore hint

From each start, walk x+1, x+2… while present. Each element is the start of at most one walk, so total work is O(n).

A · Core idea

Insert all numbers into a hash set (which also removes duplicates). Then iterate the set; for each value x, check whether x-1 is present. If it is, x sits in the middle of some run and we skip it — counting from here would be redundant. If x-1 is absent, x is the smallest element of its run, so we walk upward x+1, x+2, … while each is in the set, counting the length, and update the best.

Why it's O(n), not O(n²). The nested while loop looks dangerous, but it only ever executes for sequence starts. A run of length L has exactly one start, and its while loop runs L steps — visiting each of the run's L elements once. Summed over all runs, that's every element visited a constant number of times: O(n) total.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [100, 4, 200, 1, 3, 2]

Hash-map state

x=1

lookup 0

ValueIndex / state

1→ •

2→ •

3→ •

4→ •

100→ •

Continue scanning

0 absent → start

Final result4

C · Code with teaching comments

solution.javaJava

Hash Set — Start-Only Walk (Optimal) — optimal

3 teaching notes

1
public int longestConsecutive(int[] nums) {
2
    Set<Integer> set = new HashSet<>();
3
    for (int n : nums) set.add(n);
4
    int best = 0;
5
    for (int x : set) {
6
        // The O(n) guard — only walk from the smallest element of each run.
7
        if (!set.contains(x - 1)) {        // x starts a sequence
8
            int length = 1;
9
            int current = x;
10
            // Extend upward; each element here belongs to this run only.
11
            while (set.contains(current + 1)) {
12
                current++;
13
                length++;
14
            }
15
            // Record the longest run discovered so far.
16
            best = Math.max(best, length);
17
        }
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The 'x−1 not in set' guard is the linchpin. Without it you'd re-walk the same run from each of its members (quadratic). With it, every element participates in exactly one upward walk. This is the same 'store everything, query in O(1)' trade as Two Sum, applied to neighbour-presence.

ComplexityO(n) time, O(n) space — Building the set is O(n). The inner while loop only runs for sequence starts, and across all starts it visits each element exactly once, so the loops together are O(n) amortized.

E · Edge cases and pitfalls6nums = [] — Empty set, loop never runs, best stays 0.Explore edge cases

Edge cases handled

nums = []Empty set, loop never runs, best stays 0.
nums = [1, 1, 1]Set collapses to {1}; single run of length 1.
nums = [-3, -2, -1]Negatives work the same; run -3,-2,-1 has length 3.

Pitfalls

Omitting the x-1 guard — degrades to O(n²) by re-walking runs.
Iterating the original array instead of the set — duplicates cause repeated work.
Seeding best to 1 and returning 1 on an empty array — seed to 0.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int n : nums) set.add(n); int best = 0; for (int x : set) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the start-of-sequence guard

Without checking that x-1 is absent, every element of a run launches its own upward walk, making the algorithm O(n²) and defeating the purpose of the set.

Explore the code comparison

Don't write this

for x in num_set:
    length = 1; cur = x
    while cur + 1 in num_set:   # runs for EVERY x
        cur += 1; length += 1
    best = max(best, length)

Write this instead

for x in num_set:
    if x - 1 not in num_set:     # only true starts
        cur, length = x, 1
        while cur + 1 in num_set:
            cur += 1; length += 1
        best = max(best, length)

Iterating the array, not the set

Looping over nums (with duplicates) repeats work and can miscount; iterate the deduplicated set instead.

Explore the code comparison

Don't write this

for (int x : nums) { /* duplicates re-processed */ }

Write this instead

for (int x : set) { /* each distinct value once */ }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash set + start-only sequence walk

Code pattern to memorize

s = set(nums)
best = 0
for x in s:
    if x-1 not in s:        # x is a sequence start
        y = x
        while y+1 in s: y += 1
        best = max(best, y - x + 1)

Rules to remember

1Only begin a walk when x-1 is not in the set — that's what makes it O(n), not O(n²).
2Use a set for O(1) membership; iterate the set (not the array) to skip duplicates cheaply.
3Walk upward (x+1, x+2…); each number is the start of at most one walk.
4Track the best length as you go; don't sort (sorting is the O(n log n) fallback).
5Empty input → answer is 0; handle it before the loop or let best stay 0.

Use this pattern when

Longest run / streak of consecutive values in unordered data
Need O(n) where sorting's O(n log n) is too slow or disallowed
Membership-driven traversal ('is the neighbour present?')

Choose another pattern when

Sequence must preserve original index order → not this (that's subsequence DP)
Need the actual elements / multiple longest runs → adapt to record them
Data already sorted → a single linear scan comparing neighbours suffices

Interview takeaway

The start-check (x−1 absent) is the whole trick: it guarantees each element is touched O(1) amortized times, turning what looks quadratic into linear. It's the same 'remember everything in a set' lever as Two Sum and Contains Duplicate.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternHash set with a start-of-run guard. Reach for it when you need the longest consecutive run in O(n) on unsorted data. The 'only start from boundaries' trick to keep nested loops linear recurs in grid/island traversals too.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Same 'remember values in a hash structure for O(1) lookup' lever.
Contains Duplicate
Hash set membership in its simplest form.
Binary Tree Longest Consecutive Sequence
Coming soon
Same 'longest consecutive run' idea, walked over tree paths via DFS.

Same pattern

←

Encode and Decode Strings

Continue · Next problem

Valid Sudoku

mediumArraysLC #128Frequently asked

Longest Consecutive Sequence

LCPractice

Arrays & Hashing · 7 of 83 · 8 min

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.

In plain English

Examples

Example 1

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Note: The run 1,2,3,4 has length 4.

Example 2

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Note: 0 through 8 form a run of length 9 (the duplicate 0 doesn't matter).

Example 3

Input: nums = []
Output: 0
Note: No elements, no sequence.

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Clarifying questions4First question: Does the sequence have to appear in order in the array?Explore questions

Q1.Does the sequence have to appear in order in the array?
No — only the values matter. [100, 4, 200, 1, 3, 2] yields the run 1,2,3,4 even though they're scattered.
Q2.Are duplicates possible, and do they affect the count?
Yes, duplicates can appear; they don't lengthen a run. Using a set naturally collapses them.
Q3.What should an empty array return?
0 — there's no sequence.
Q4.Is sorting acceptable?
It gives the right answer in O(n log n), but the problem demands O(n), so we use the hash-set method.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can hit O(n) without sorting by using a hash set and the start-of-sequence optimization — and whether you can justify the linear bound despite a while-loop inside a for-loop.

Where candidates slip

Walking a sequence from every element (O(n²)), or sorting and calling it optimal when O(n) was required.

How to stand out

Explain the amortized O(n) argument: the inner while loop only runs for sequence starts, and across all starts it visits each element once.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort Then Scan	`O(n log n)`	`O(1)`	The intuitive answer — but it's O(n log n), so flag that it misses the O(n) requirement.	Read
2	Hash Set — Start-Only Walk (Optimal)Optimal	`O(n)`	`O(n)`	The required O(n) answer. Lead with the 'only start from sequence beginnings' insight.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort Then Scan

TimeO(n log n)SpaceO(1)

The intuitive answer — but it's O(n log n), so flag that it misses the O(n) requirement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the numbers were in order, how would you measure the longest unbroken run?

2Hint 2Explore hint

Sort, then scan once counting how long each consecutive run lasts, resetting on gaps.

3Hint 3Explore hint

Skip duplicates while scanning. It works, but sorting costs O(n log n) — not the required O(n).

A · Core idea

Why mention it. It's the natural first instinct and is easy to get right. But the problem explicitly asks for O(n), so this is the baseline you improve on with the hash-set method.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [100, 4, 200, 1, 3, 2]

1→2→3→4

each +1, extend run

Statecurrent=4, best=4

Final result4

C · Code with teaching comments

solution.javaJava

Sort Then Scan — reference

2 teaching notes

1
public int longestConsecutive(int[] nums) {
2
    if (nums.length == 0) return 0;
3
    Arrays.sort(nums);
4
    int best = 1, current = 1;
5
    for (int i = 1; i < nums.length; i++) {
6
        // Skip duplicates so they don't reset or inflate the run.
7
        if (nums[i] == nums[i - 1]) continue;
8
        // Exactly one more → the run continues.
9
        if (nums[i] == nums[i - 1] + 1) {
10
            current++;
11
        } else {
12
            current = 1;
13
        }
14
        best = Math.max(best, current);
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Sorting makes 'consecutive' a local property (adjacent elements), which is easy to scan — but paying O(n log n) to get locality is exactly the cost the hash-set approach avoids.

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n); the linear scan after is O(n). O(1) extra space if sorting in place.

E · Edge cases and pitfalls3Not handling duplicates — they can falsely reset or break runs.Explore edge cases

Pitfalls

Not handling duplicates — they can falsely reset or break runs.
Returning 0 for a non-empty array because best wasn't seeded to 1.
Claiming O(n) — sorting makes it O(n log n).

03.2

Approach 2 of 2 · Optimal

Hash Set — Start-Only Walk (Optimal)

TimeO(n)SpaceO(n)

The required O(n) answer. Lead with the 'only start from sequence beginnings' insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Put everything in a set for O(1) membership. How do you avoid recounting the same run from different elements?

2Hint 2Explore hint

A number x begins a sequence only if x-1 is NOT in the set. Start counting just from those.

3Hint 3Explore hint

From each start, walk x+1, x+2… while present. Each element is the start of at most one walk, so total work is O(n).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [100, 4, 200, 1, 3, 2]

Hash-map state

x=1

lookup 0

ValueIndex / state

1→ •

2→ •

3→ •

4→ •

100→ •

Continue scanning

0 absent → start

Final result4

C · Code with teaching comments

solution.javaJava

Hash Set — Start-Only Walk (Optimal) — optimal

3 teaching notes

1
public int longestConsecutive(int[] nums) {
2
    Set<Integer> set = new HashSet<>();
3
    for (int n : nums) set.add(n);
4
    int best = 0;
5
    for (int x : set) {
6
        // The O(n) guard — only walk from the smallest element of each run.
7
        if (!set.contains(x - 1)) {        // x starts a sequence
8
            int length = 1;
9
            int current = x;
10
            // Extend upward; each element here belongs to this run only.
11
            while (set.contains(current + 1)) {
12
                current++;
13
                length++;
14
            }
15
            // Record the longest run discovered so far.
16
            best = Math.max(best, length);
17
        }
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6nums = [] — Empty set, loop never runs, best stays 0.Explore edge cases

Edge cases handled

nums = []Empty set, loop never runs, best stays 0.
nums = [1, 1, 1]Set collapses to {1}; single run of length 1.
nums = [-3, -2, -1]Negatives work the same; run -3,-2,-1 has length 3.

Pitfalls

Omitting the x-1 guard — degrades to O(n²) by re-walking runs.
Iterating the original array instead of the set — duplicates cause repeated work.
Seeding best to 1 and returning 1 on an empty array — seed to 0.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int n : nums) set.add(n); int best = 0; for (int x : set) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the start-of-sequence guard

Without checking that x-1 is absent, every element of a run launches its own upward walk, making the algorithm O(n²) and defeating the purpose of the set.

Explore the code comparison

Don't write this

for x in num_set:
    length = 1; cur = x
    while cur + 1 in num_set:   # runs for EVERY x
        cur += 1; length += 1
    best = max(best, length)

Write this instead

for x in num_set:
    if x - 1 not in num_set:     # only true starts
        cur, length = x, 1
        while cur + 1 in num_set:
            cur += 1; length += 1
        best = max(best, length)

Iterating the array, not the set

Looping over nums (with duplicates) repeats work and can miscount; iterate the deduplicated set instead.

Explore the code comparison

Don't write this

for (int x : nums) { /* duplicates re-processed */ }

Write this instead

for (int x : set) { /* each distinct value once */ }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash set + start-only sequence walk

Code pattern to memorize

s = set(nums)
best = 0
for x in s:
    if x-1 not in s:        # x is a sequence start
        y = x
        while y+1 in s: y += 1
        best = max(best, y - x + 1)

Rules to remember

1Only begin a walk when x-1 is not in the set — that's what makes it O(n), not O(n²).
2Use a set for O(1) membership; iterate the set (not the array) to skip duplicates cheaply.
3Walk upward (x+1, x+2…); each number is the start of at most one walk.
4Track the best length as you go; don't sort (sorting is the O(n log n) fallback).
5Empty input → answer is 0; handle it before the loop or let best stay 0.

Use this pattern when

Longest run / streak of consecutive values in unordered data
Need O(n) where sorting's O(n log n) is too slow or disallowed
Membership-driven traversal ('is the neighbour present?')

Choose another pattern when

Sequence must preserve original index order → not this (that's subsequence DP)
Need the actual elements / multiple longest runs → adapt to record them
Data already sorted → a single linear scan comparing neighbours suffices

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Same 'remember values in a hash structure for O(1) lookup' lever.
Contains Duplicate
Hash set membership in its simplest form.
Binary Tree Longest Consecutive Sequence
Coming soon
Same 'longest consecutive run' idea, walked over tree paths via DFS.

Same pattern

←

Encode and Decode Strings

Continue · Next problem

Valid Sudoku