Longest Consecutive Sequence

Problem in Plain English

Given an unsorted array of integers, return the length of the longest run of consecutive integers it contains. The order in the array does not matter and the algorithm must run in linear time.

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. Sorting would place consecutive values side by side, a hash set instead supports expected constant-time membership checks without sorting.

Constraints

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

Examples

Example 1

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4

The longest consecutive 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

The longest consecutive run is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has length 9.

Example 3

Input: nums = [1, 0, 1, 2]
Output: 3

The distinct values 0, 1, and 2 form one run of length 3. The second occurrence of 1 adds no new consecutive value.

Example 4

Input: nums = []
Output: 0

No integers means there is no run to count.

Intuition

Consecutive values differ by one; their positions in the array do not matter. In [100, 4, 200, 1, 3, 2], the values 1 through 4 form a run even though they are scattered. Store values in a set for quick membership checks. Start counting only where the previous integer is missing: 1 starts the run, while 2, 3, and 4 do not.

Approaches

Sorting

Solution Details

Reveal Sorting: intuition, complexity, and code

Intuition

Sorting lines every run of consecutive values up side by side, so one scan counting neighbors that differ by exactly one finds the longest run. The sort itself costs $O(n log n)$ , which misses the required linear bound and motivates the hash set approach.

Step-by-Step Logic

If nums is empty, return 0; otherwise sort ascending. Example 1 becomes [1, 2, 3, 4, 100, 200]. The shown code sorts the input in place.
Initialize current = 1 and longest = 1. Scan from the second value, comparing each with the preceding sorted value.
Skip equal neighbors: a duplicate contributes no new integer and must not break the run.
If the next distinct value is previous + 1, increment current; otherwise record longest = max(longest, current) and reset current to 1. Here 2, 3, and 4 extend the run; 100 and 200 break it.
Return max(longest, current) to include a run ending at the final element. Example 1 returns 4.

Why It Works

In sorted order, all distinct values of a consecutive run are adjacent. Ignoring equal neighbors preserves that run. A gap greater than one ends it because the missing integer cannot appear elsewhere in sorted order. current therefore measures the current run, longest records completed runs, and the final maximum includes the last run.

Dry Run

Sorting: variable states at each step
index	value	previous	`current`	`longest`
initial	`1`	none	`1`	`1`
`1`	`2`	`1`	`2`	`1`
`2`	`3`	`2`	`3`	`1`
`3`	`4`	`3`	`4`	`1`
`4`	`100`	`4`	`1`	`4`
`5`	`200`	`100`	`1`	`4`, answer `4`

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Sorting costs O(n log n), followed by one O(n) scan. The scan uses O(1) counters, but that is not the full space cost: Python sorting can require O(n) temporary storage, Java primitive sorting uses a smaller stack, and JavaScript sort storage depends on the engine. O(n) is a conservative auxiliary bound for these implementations. Sorting mutates nums; a defensive copy would also need O(n) space. This approach does not meet the required linear-time bound.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int longestConsecutive(int[] nums) {5        if (nums.length == 0) {6            return 0;7        }8        Arrays.sort(nums);9        int longest = 1;10        int current = 1;11        for (int i = 1; i < nums.length; i++) {12            if (nums[i] != nums[i - 1]) {13                if (nums[i] == nums[i - 1] + 1) {14                    current++;15                } else {16                    longest = Math.max(longest, current);17                    current = 1;18                }19            }20        }21        return Math.max(longest, current);22    }23}

Hints

Hint 1

Sorting first turns the problem into a neighbor-counting scan, but check what that costs on 10^5 elements.

Hint 2

Linear time needs average

O(1)

membership tests, which points at storing every value in a hash set.

Hint 3

Only measure runs forward from values whose predecessor num - 1 is missing, so each run is counted exactly once.

Edge Cases

An empty array has no run at all and returns 0.
Duplicates such as [1, 2, 0, 1] must not inflate the run; the set collapses them and the sort skips equal neighbors.
Negative values work identically: [-2, 0, -1] returns 3.
Separated values such as [10, 30, 50] return 1; a single value also returns 1.
Values at -1000000000 and 1000000000 are allowed. Their neighbor checks still fit Java int and exact JavaScript integer arithmetic.

Common Mistakes and Interview Tips

Counting a forward run from every value instead of only run starts, which turns the hash set scan back into $O(n^2)$ on long runs.
Forgetting to skip equal neighbors in the sorting scan, so a duplicate wrongly resets the current run.
Looping over nums rather than distinct set values can recount a long run many times when its start is duplicated.
Interview tip: explain the total successor visits across all runs to justify the nested loops, and state the expected constant-time hashing assumption.
Claiming the sorting solution uses constant total space ignores the sorting implementation; also disclose that it changes the input.

Key Takeaway

For consecutiveness questions, store values in a hash set and anchor each piece of work at a start condition so no element is processed twice.