Longest Consecutive Sequence
In linear time, find the length of the longest run of consecutive integer values in an unsorted array. Repeated values do not extend a run.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1.Expected result
The maximum run length.Case 1
Input
20 4 2 3 1 2
Expected output
4
Case 2
Input
8 10 12
Expected output
1
Case 3
Input
-2 -1 0 2
Expected output
3
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Sorting and scanning runs is O(nlog n); the problem asks for O(n). n ≤ 10^5. Put the values in a hash set. From each x still in the set, walk right until the run breaks, store that length at the start, and let earlier starts concatenate. Each number enters and leaves the set once.
We can use a hash table s to store all the elements in the array, a variable ans to record the length of the longest consecutive sequence, and a hash table d to record the length of the consecutive sequence each element x belongs to.
Next, we iterate through each element x in the array, using a temporary variable y to record the maximum value of the current consecutive sequence, initially y = x. Then, we continuously try to match y+1, y+2, y+3, \dots until we can no longer match. During this process, we remove the matched elements from the hash table s. The length of the consecutive sequence that the current element x belongs to is d[x] = d[y] + y - x, and then we update the answer ans = \max(ans, d[x]).
After the iteration, we return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int x : nums) {
s.add(x);
}
int ans = 0;
Map<Integer, Integer> d = new HashMap<>();
for (int x : nums) {
int y = x;
while (s.contains(y)) {
s.remove(y++);
}
d.put(x, d.getOrDefault(y, 0) + y - x);
ans = Math.max(ans, d.get(x));
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.