72. Unbroken Number Chain
A museum hands out numbered entry tickets, and the array nums lists the serial numbers scanned at the gate today, in no particular order. Some serials may be scanned more than once.
A chain is a group of serials that form consecutive integers when sorted, such as 31, 32, 33. Look at the distinct serials in nums and return the length of the longest chain you can build from them. The serials do not need to be next to each other in the array, and a repeated serial only counts once. Try to do better than sorting the whole array.
Example 1
- Input:
- nums = [41,12,40,13,39,14,15,90]
- Output:
- 4
- Explanation:
The serials 12, 13, 14, 15 form a chain of length 4, longer than the chain 39, 40, 41 of length 3.
Example 2
- Input:
- nums = [8,8,8,6]
- Output:
- 1
- Explanation:
The distinct serials are 8 and 6, which are not consecutive, so the longest chain has length 1.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)