Compile Ready
Module 5 · Advanced Arrays

Longest Consecutive Sequence

MediumProblem 12 of 18 8 min read ~20 min to solve LeetCode
ArrayHash SetSequenceMembershipLinear Scan
Asked atAmazonGoogleMicrosoftMetaOracle

Problem Statement

Given an unsorted integer array nums, return the length of the longest sequence of consecutive integer values. The sequence values do not need to appear next to each other in the original array.

Input

An integer array nums, possibly containing duplicates and values in any order.

Output

An integer: the number of values in the longest run of consecutive integers.

Constraints

  • •0 <= nums.length <= 10^5
  • •-10^9 <= nums[i] <= 10^9
  • •The required algorithm should run in O(n) time

Examples

Example 1

Input: 
nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest run is **[1,2,3,4]**, which has length 4.

Example 2

Input: 
nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: The values 0 through 8 are all present, so the longest consecutive run has length 9.

Example 3

Input: 
nums = []
Output: 0
Explanation: With no values, there is no consecutive sequence.

Learning Objectives

  • Recognise that original order is irrelevant and membership queries are the real operation.
  • Use a HashSet to deduplicate values and test neighbours in O(1) average time.
  • Start counting only from values whose predecessor is absent.
  • Prove that each value is walked as part of a sequence at most once overall.

Intuition

Pattern Recognition

The phrase consecutive sequence can tempt you to sort, but sorting costs O(n log n). Since the required output ignores original order, the useful operation is fast membership: is x + 1 present after x?

The HashSet gives O(1) average membership, but starting a walk from every value would still repeat work. The key signal for a true run start is that x - 1 is absent. Only then should you walk x, x + 1, x + 2 and count. Every non-start value is skipped because it will be counted by the start of its run.

Common mistakes

  • ×Sorting the array even though the prompt asks for an O(n) solution.
  • ×Starting a count from every number, which can degrade to O(n^2) on a long run.
  • ×Letting duplicates inflate the length of a run.
  • ×Confusing consecutive values with consecutive positions in the original array.

Algorithm Explanation

Key idea

Put every value into a HashSet. A value x is the beginning of a run only when x - 1 is not in the set. From such starts, walk upward while the next consecutive value exists and update the best length.

Walkthrough

For nums = [100,4,200,1,3,2], the set contains 1,2,3,4,100,200. Value 1 has no predecessor 0, so it starts a run. Walking 1, 2, 3, 4 gives length 4. Values 2, 3, and 4 are skipped as starts because each has a predecessor in the set. Values 100 and 200 each start length-1 runs. The best remains 4.

Algorithm

  1. Insert every number into a HashSet to remove duplicates and support membership tests.
  2. Set best = 0.
  3. For each value x in the set, check whether x - 1 is absent.
  4. If x is a run start, set current = x and length = 1.
  5. While current + 1 exists in the set, advance current and increment length.
  6. Update best with length.
  7. Return best.

Solutions

Solution: HashSet starts-only scan

The set turns neighbour lookup into constant average time. The starts-only check prevents repeated walking because each consecutive run is traversed exactly once from its smallest value.

Step-by-step

  1. Insert all values into a HashSet so duplicates disappear.
  2. Iterate through the set values.
  3. Skip a value if its predecessor exists because it is inside a run that starts earlier.
  4. For a true start, walk upward while the next value exists, counting the run length.
  5. Update the best length after each completed run.
Time

O(n)

Space

O(n)

Each unique value is inserted once and belongs to at most one upward walk from a run start.

Java implementation

Loading…

Dry Run

Sample input

nums = [100,4,200,1,3,2]. The HashSet is {1,2,3,4,100,200}. Track only true run starts.

candidatepredecessor presentis run startsequence walkedbest after candidate
1noyes1 -> 2 -> 3 -> 44
2yes, 1 existsnoskip4
3yes, 2 existsnoskip4
4yes, 3 existsnoskip4
100noyes1004
200noyes2004

Only value 1 starts the length-4 run. The starts-only rule avoids recounting from 2, 3, and 4.

Interview Tips

Mention sorting as the obvious O(n log n) baseline, then explain why the required O(n) solution needs membership instead of ordering. The most important sentence is: only count from x when x - 1 is absent. That single guard is what turns repeated neighbour walks into overall linear work.

Likely follow-ups

  • How would the solution change if you had to return the actual sequence values?
  • How would you solve it if memory were limited and sorting were allowed?
  • How would you handle a stream of numbers and answer after each insertion?
  • How would duplicates be reported if the output required original indices?

Similar Problems

Contains Duplicate
EasyThe basic HashSet membership pattern.
First Missing Positive
HardAlso reasons about which positive values are present.
Top K Frequent Elements
MediumAnother problem where hashing summarizes an unsorted array.
Longest Harmonious Subsequence
EasyUses value counts and neighbour relationships.
Number of Longest Increasing Subsequence
MediumContrasts arbitrary increasing subsequences with exact consecutive values.

Key Takeaways

  • Consecutive sequence length depends on value membership, not original positions.
  • A HashSet removes duplicates and supports neighbour checks.
  • Only values without a predecessor should start a run.
  • The starts-only invariant keeps the total walking work linear.
Reusable template: For unsorted consecutive-value problems, hash all values, start only at values with no predecessor, and walk forward while successors exist.