#128 Longest Consecutive Sequence
frequently reported atBloombergWalmartAmazonByteDance / TikTokGoogleMicrosoft
the problem
In plain words
Given an unsorted array, return the length of the longest run of consecutive integers (like 1, 2, 3, 4) that can be formed from its values. It must run in O(n).
in nums = [100,4,200,1,3,2]
out 4
1, 2, 3, 4.
in nums = [0,3,7,2,5,8,4,6,0,1]
out 9
- 0 ≤ n ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)Union-Find (DSU)
Only start counting at a number x whose predecessor x − 1 is not in the set. Then every run is walked exactly once.
solutions
From brute force to optimal
Put everything in a set; from each value, count x+1, x+2, … while present.
- set = all values.
- For each x in set, extend upward while set contains the next number.
A run of length L is re-walked from each of its L members: 1 + 2 + … + n.
The set.
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); int best = 0; for (int x : set) { int length = 1; while (set.contains(x + length)) length++; // walks up from EVERY number best = Math.max(best, length); } return best; }}After sorting, a run is a stretch where each value is the previous + 1 (skip equal values).
- Sort a copy.
- Equal to previous → skip; previous + 1 → run++; else run = 1.
- Track the best run.
Sorting. It breaks the O(n) requirement but is a fine first answer.
The sorted copy.
class Solution { public int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; int[] a = nums.clone(); Arrays.sort(a); int best = 1, run = 1; for (int i = 1; i < a.length; i++) { if (a[i] == a[i - 1]) continue; // duplicate: neither extends nor breaks if (a[i] == a[i - 1] + 1) run++; // next number in the run else run = 1; // gap: start a new run best = Math.max(best, run); } return best; }}x starts a run iff x − 1 is missing. Only starts walk upward.
- set = all values.
- For each x in the set: skip if set contains x − 1.
- Otherwise walk x+1, x+2, … and record the length.
Each value is visited once by the outer loop and at most once by a walk, from its run's start.
The set.
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); int best = 0; for (int x : set) { // iterate the SET: duplicates are skipped if (set.contains(x - 1)) continue; // not the start of a run → someone else counts it int length = 1; while (set.contains(x + length)) length++; best = Math.max(best, length); } return best; }}Dry run
Map-based DSU over the values: union x with x + 1 when both exist; the biggest set is the answer.
- parent.put(x, x), size.put(x, 1) for every value.
- For each x with x + 1 present: union by size.
- Answer = max size seen (1 if non-empty).
n near-constant unions over average O(1) hash lookups.
The parent and size maps.
class Solution { private final Map<Integer, Integer> parent = new HashMap<>(); private final Map<Integer, Integer> size = new HashMap<>(); private int find(int x) { int p = parent.get(x); if (p != x) { p = find(p); parent.put(x, p); } return p; } public int longestConsecutive(int[] nums) { for (int x : nums) { parent.put(x, x); size.put(x, 1); } // duplicates just reset to themselves int best = nums.length == 0 ? 0 : 1; for (int x : parent.keySet()) { if (!parent.containsKey(x + 1)) continue; // join x with its right neighbour int ra = find(x), rb = find(x + 1); if (ra == rb) continue; if (size.get(ra) < size.get(rb)) { int t = ra; ra = rb; rb = t; } parent.put(rb, ra); size.put(ra, size.get(ra) + size.get(rb)); best = Math.max(best, size.get(ra)); } return best; }}in the room
How to say it in the interview
talk track
- Mention sorting first (O(n log n)), then say the requirement is O(n), so you need O(1) membership tests: a HashSet.
- Explain the "only from starts" rule and why it makes the nested while loop O(n) in total.
- If asked for another way: Union-Find merges each x with x + 1. It's more code, but it generalises to "merge neighbours" problems.
traps
- Looping over
numsinstead of the set: duplicates of a start re-walk the same run. - Forgetting the empty array (answer 0).
what they ask next
Follow-ups
Why not always use the union-find version?
It's near O(n) too, but needs two maps and a find/union pair. The set trick is shorter and easier to get right under pressure; DSU shines when groups also merge later (online updates).
before you submit
Edge cases to test
- Empty array → 0.
- Duplicates ([1,0,1,2] → 3) — loop over the set, not the array.
- Negative runs ([-3,-2,-1]) and far-apart values (10⁹ and −10⁹).
practise next
Similar problems
- #217Contains DuplicateEasyin Hashing
- #41First Missing PositiveHardin Arrays & Strings
- #547Number of ProvincesMediumin Union-Find & MST