Longest Consecutive Sequence
Longest Consecutive Sequence is a medium arrays & hashing problem solved with the hash set lookup pattern.
The best approach, optimal (hash set, count only from run starts), runs in O(n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (extend each value by searching) up.
Problem
Given an unsorted integer array nums, return the length of the longest run of consecutive integers whose values all appear in nums. A run is a set of values like x, x + 1, x + 2, …; the values may appear anywhere in the array, in any order.
Repeated values count once. Try to solve it in O(n) time.
Examples
Example 1
- Input
nums = [10, 4, 20, 3, 11, 5, 2]- Output
4- Why
- The values 2, 3, 4, 5 form a run of four consecutive integers; 10, 11 is only a run of two.
Example 2
- Input
nums = [7, -1, 0, 7, 1, -2, 8]- Output
4- Why
- -2, -1, 0, 1 is the longest run. The repeated 7 does not lengthen 7, 8.
Example 3
- Input
nums = []- Output
0- Why
- No values, no run.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9- Aim for O(n) time.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (extend each value by searching) | O(n³) | O(1) |
| Better (sort, then count runs) | O(n log n) | O(n) |
| Optimal (hash set, count only from run starts) | O(n) | O(n) |
1Brute force (extend each value by searching)
O(n³)Each of the n starts can extend up to n times, and each extension scans the n elements.O(1)Only counters.Treat every value as a possible start and keep looking for the next integer by scanning the whole array, counting how far the run goes.
- For each x in nums: cur = x, len = 1.
- While the array contains cur + 1 (checked with a linear scan), increment cur and len.
- Keep the largest len.
class Solution {
public int longestConsecutive(int[] nums) {
int best = 0;
for (int x : nums) {
int cur = x, len = 1;
while (contains(nums, cur + 1)) {
cur++;
len++;
}
best = Math.max(best, len);
}
return best;
}
private boolean contains(int[] nums, int v) {
for (int x : nums) if (x == v) return true;
return false;
}
}class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
best = 0
for x in nums:
cur, length = x, 1
while any(y == cur + 1 for y in nums):
cur += 1
length += 1
best = max(best, length)
return bestclass Solution {
bool contains(const vector<int>& nums, int v) {
for (int x : nums) if (x == v) return true;
return false;
}
public:
int longestConsecutive(vector<int>& nums) {
int best = 0;
for (int x : nums) {
int cur = x, len = 1;
while (contains(nums, cur + 1)) {
cur++;
len++;
}
best = max(best, len);
}
return best;
}
};function longestConsecutive(nums) {
let best = 0;
for (const x of nums) {
let cur = x, len = 1;
while (nums.includes(cur + 1)) {
cur++;
len++;
}
best = Math.max(best, len);
}
return best;
}2Better (sort, then count runs)
O(n log n)Sorting dominates; the walk is O(n).O(n)The sorted copy.Sort a copy of the array so consecutive integers sit next to each other. Walk it once: equal neighbors are skipped, a neighbor that is exactly one larger extends the run, and anything else starts a new run.
- Sort the values.
- For i from 1: if a[i] == a[i - 1], skip; if a[i] == a[i - 1] + 1, run++; otherwise run = 1.
- Track the largest run (0 for an empty array).
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;
if (a[i] == a[i - 1] + 1) run++;
else run = 1;
best = Math.max(best, run);
}
return best;
}
}class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
a = sorted(nums)
best = run = 1
for i in range(1, len(a)):
if a[i] == a[i - 1]:
continue
if a[i] == a[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestclass Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> a = nums;
sort(a.begin(), a.end());
int best = 1, run = 1;
for (int i = 1; i < (int)a.size(); i++) {
if (a[i] == a[i - 1]) continue;
if (a[i] == a[i - 1] + 1) run++;
else run = 1;
best = max(best, run);
}
return best;
}
};function longestConsecutive(nums) {
if (nums.length === 0) return 0;
const a = [...nums].sort((x, y) => x - y);
let best = 1, run = 1;
for (let i = 1; i < a.length; i++) {
if (a[i] === a[i - 1]) continue;
if (a[i] === a[i - 1] + 1) run++;
else run = 1;
best = Math.max(best, run);
}
return best;
}3Optimal (hash set, count only from run starts)
O(n)Each value is inserted once, checked once as a possible start, and stepped over by at most one run walk.O(n)The hash set holds up to n values.Put every value in a hash set. A value v starts a run exactly when v - 1 is not in the set. From each start, count upward while v + 1, v + 2, … are present. Every value is visited by at most one such walk, so the total work is linear.
- Add all values to a set.
- For each v in the set: if v - 1 is in the set, skip it (it is not a start).
- Otherwise count len while v + len is in the set, and keep the largest len.
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int v : set) {
if (set.contains(v - 1)) continue;
int len = 1;
while (set.contains(v + len)) len++;
best = Math.max(best, len);
}
return best;
}
}class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
best = 0
for v in s:
if v - 1 in s:
continue
length = 1
while v + length in s:
length += 1
best = max(best, length)
return bestclass Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int best = 0;
for (int v : s) {
if (s.count(v - 1)) continue;
int len = 1;
while (s.count(v + len)) len++;
best = max(best, len);
}
return best;
}
};function longestConsecutive(nums) {
const s = new Set(nums);
let best = 0;
for (const v of s) {
if (s.has(v - 1)) continue;
let len = 1;
while (s.has(v + len)) len++;
best = Math.max(best, len);
}
return best;
}Edge cases to test
- Empty array
- Duplicates inside a run, which must be counted once
- Negative numbers and runs that cross zero
- All values equal: the answer is 1
- Values far apart, so every run has length 1
Hints
Hint 1
Order in the array does not matter; only which values are present. Sorting puts runs next to each other, but costs O(n log n).
Hint 2
Put every value in a hash set so you can ask 'is v + 1 present?' in O(1).
Hint 3
Only start counting from a value v whose v - 1 is NOT in the set. Then each run is walked exactly once.
FAQ
What is the best time complexity for Longest Consecutive Sequence?
Optimal (hash set, count only from run starts) runs in O(n) time and O(n) extra space. Each value is inserted once, checked once as a possible start, and stepped over by at most one run walk.
Which pattern does Longest Consecutive Sequence use?
It is a arrays & hashing problem that uses the hash set lookup pattern. Other problems with the same pattern: Contains Duplicate, Fair Candy Swap, Maximize Area of Square Hole in Grid.
Is there a brute force solution for Longest Consecutive Sequence?
Yes. Brute force (extend each value by searching) takes O(n³) time and O(1) space. Treat every value as a possible start and keep looking for the next integer by scanning the whole array, counting how far the run goes.
Which edge cases should I test for Longest Consecutive Sequence?
Empty array; Duplicates inside a run, which must be counted once; Negative numbers and runs that cross zero; All values equal: the answer is 1; Values far apart, so every run has length 1.