Only start at the start
Find the longest run of consecutive values with a set. About 10 minutes.
A set answers "is it here?" instantly
You're given numbers in any order, like 100, 4, 200, 1, 3, 2, and asked for the longest run of consecutive values: here 1, 2, 3, 4. Sorting would work, but there's a faster way.
Put every number in a set. Now "is 5 here?" is one quick lookup instead of a search. From any number you can count upwards, asking "is the next one here? and the next?", until one is missing.
- best
- 1
x = 100. Is 99 in the set? No, so a run starts here. Count up: 101? Missing. A run of 1.
Only count from the start of a run
Counting upwards from every number would walk the same run again and again: from 1, then from 2, then from 3. The fix is a simple question before you start: is the number just below this one in the set? If it is, this number is in the middle of a run, so skip it. The run will be counted from its real start.
That way every run is walked exactly once.
seen = set(nums)
best = 0
for x in seen:
if x - 1 not in seen:
length = 1
while x + length in seen:
length += 1
best = max(best, length)
return bestThe set is 1, 2, 3, 10, 11. Which numbers do you start counting from?
- A1 and 10
- BAll five
- COnly 1
Show the answer
1 and 10. 0 and 9 aren't there, so 1 and 10 start runs. The others are in the middle of one.
Longest streak
You get a list of whole numbers in any order, possibly with repeats. Return the length of the longest run of consecutive values that are all present (like 1, 2, 3, 4). An empty list has no run: return 0.
nums = [100, 4, 200, 1, 3, 2] → 4
0 ≤ n ≤ 1,000,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000 · aim for about n steps, no sorting