Given an unsorted integer array nums, return the length of the longest run of consecutive integers (like 4, 5, 6, 7) whose values all appear in the array. The elements do not need to be next to each other in nums. Aim for O(n) time.
Example 1
Input: nums = [100,4,200,1,3,2]
Output: 4
The values 1, 2, 3, 4 are all present, a run of length 4.
Example 2
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Every value from 0 to 8 is present.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Hints
Frequently asked at: Google, Amazon, Microsoft, Uber, PhonePe
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting and scanning for runs is O(n log n). Walking upward from every number using a set could be O(n^2) on a long run, because each element of the run restarts the walk. The fix: only start a walk from the first number of a run, that is a number x where x - 1 is missing. Every number is then visited at most twice overall, giving O(n).
Algorithm
- Put all numbers into a hash set.
- For each
xin the set, skip it ifx - 1is in the set. - Otherwise walk
y = x, x+1, x+2, ...whileyis in the set, counting the length. - Keep the longest length and return it (0 for an empty array).
Time:
O(n)Space: O(n)Interview tip: Loop over the set, not the original array: with many duplicates of a run start, iterating the array can repeat the same walk many times.
class Solution: def longestConsecutive(self, nums: List[int]) -> int: s = set(nums) best = 0 for x in s: if x - 1 in s: continue # not the start of a run length = 1 while x + length in s: length += 1 best = max(best, length) return bestCtrl + Enter runs the examples