Longest run of consecutive numbers
MediumStuck?
Show a hintHide the hint
Put everything in a set. Only start counting from a number whose predecessor is missing, because that is the start of a run.
The idea behind this problem
Next in this lesson
Best run after k changesGiven a list of numbers in any order, find the length of the longest run of consecutive values. The numbers do not have to be next to each other in the list.
Worked example#
For [100, 4, 200, 1, 3, 2] the consecutive runs hiding in there are:
| run | length |
|---|---|
| 1, 2, 3, 4 | 4 |
| 100 | 1 |
| 200 | 1 |
So the answer is 4.
Sorting would work and costs n log n. There is a neater way in one pass.
Put everything in a set. Then for each number, ask whether the number one below it is also present. If it is, this number is in the middle of a run and somebody else will count it. If it is not, this is the start of a run, so count upward from here.
That check is what keeps it fast: each run is walked exactly once, from its own start, no matter how many times you look at it.
Constraints#
0 <= n <= 100000-10^9 <= nums[i] <= 10^9
Input
nums is a count then that many integers.
Output
The length of the longest consecutive run.
Examples
Input
6 100 4 200 1 3 2
Output
4
1, 2, 3, 4 are all present, so the longest run is four long.
Input
4 1 2 0 1
Output
3
0, 1, 2 form a run. The repeated 1 does not make it longer.
Input
1 5
Output
1
A single number is a run of one.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.