Longest Consecutive Sequence
You're given an unsorted integer array nums. Return the length of the longest run of consecutive integers (such as 5, 6, 7, 8) whose values all appear somewhere in nums. The values can sit anywhere in the array and in any order, so they don't need to be adjacent. Repeated values count only once. Your algorithm must run in O(n) time. An empty array returns 0.
Examples
nums = [100,4,200,1,3,2] returns 4
The values 1, 2, 3 and 4 all appear, at different positions, giving a run of length 4. 100 and 200 have no neighboring values in the array.
nums = [0,3,7,2,5,8,4,6,0,1] returns 9
Every integer from 0 through 8 appears, so the run 0, 1, ..., 8 has length 9. The second 0 adds nothing.
nums = [1,0,1,2] returns 3
0, 1 and 2 are present. The repeated 1 is counted once, so the answer is 3, not 4.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Hints
Sorting would line the runs up, but it costs O(n log n). What would let you ask whether the value x + 1 is present in constant time?
Put every value in a hash set. A run can only begin at a value x where x - 1 is not in the set.
For each value x in the set with no x - 1, count upward through x + 1, x + 2, ... while those values are in the set, and keep the longest count. Each value is visited by at most one such walk, so the total is O(n).
Drill This: Your Approach First
Approach
Load every value into a hash set, which gives O(1) membership checks and drops duplicates. A value x can only start a run if x - 1 is missing, so for each such start walk x + 1, x + 2, ... while the set contains them and record the run length. Because walks begin only at run starts, each value is stepped over by at most one walk. O(n) time and O(n) space for the set.
Time
O(n)
Space
O(n)
Pitfall
Solutions
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int best = 0;
for (int num : set) {
if (set.contains(num - 1)) continue;
int length = 1;
while (set.contains(num + length)) length++;
best = Math.max(best, length);
}
return best;
}
}class Solution:
def longestConsecutive(self, nums) -> int:
num_set = set(nums)
best = 0
for num in num_set:
if num - 1 in num_set:
continue
length = 1
while num + length in num_set:
length += 1
best = max(best, length)
return best