You get an unsorted integer array nums. A run is a set of whole numbers that follow one another with no gaps, such as 6, 7, 8, 9. Return the length of the longest run whose every number appears in nums.
The numbers can sit anywhere in the array, in any order. A value that appears more than once still counts once in a run. An empty array has no run, so its answer is 0.
Sorting first works, but there is an O(n) solution that never sorts.
10, 11, 12, 13 are all present, which is a run of 4. The other run, 3, 4, 5, has only 3.
The longest run is 6, 7, 8, 9. The second 7 adds nothing, and -2, -1, 0 is a run of 3.
There are no numbers, so there is no run.
Constraints
0 <= nums.length <= 10⁵-10⁹ <= nums[i] <= 10⁹Put every number in a hash set. A run can only start at a value v where v - 1 is missing.
Forget where the numbers sit in the array. All that matters is which values are present, so put them in a hash set. Then "is v + 1 here?" is one quick lookup, and a run is just a value you can keep adding 1 to while the answer is yes.
Time O(n)Space O(n)
The full walkthrough and code are part of Premium
4