Longest Consecutive Run in an Array
Problem
Given an unsorted integer array (possibly with duplicates), return the length of the longest sequence of consecutive integers it contains. Solve it in O(n) on average.
Drop everything into a set. Only start counting a run from a value that has no predecessor in the set — otherwise we'd double-count. From a true run start, walk +1, +1, +1 until the chain breaks.
Input
nums = [102, 4, 200, 1, 3, 2, 101, 100]Output
4The run 1, 2, 3, 4 has length 4 (longer than 100, 101, 102 of length 3).
def longest_run(nums):
s = set(nums)
best = 0
for v in s:
if v - 1 in s:
continue
cur, length = v, 1
while cur + 1 in s:
cur += 1
length += 1
if length > best:
best = length
return bestfunction longestRun(nums) {
const set = new Set(nums);
let best = 0;
for (const v of set) {
if (set.has(v - 1)) continue;
let cur = v, length = 1;
while (set.has(cur + 1)) { cur++; length++; }
if (length > best) best = length;
}
return best;
}class Solution {
public int longestRun(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 cur = v, length = 1;
while (set.contains(cur + 1)) { cur++; length++; }
if (length > best) best = length;
}
return best;
}
}int longestRun(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 cur = v, length = 1;
while (s.count(cur + 1)) { cur++; length++; }
if (length > best) best = length;
}
return best;
}