Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Longest Consecutive Sequence

Hash Mapshard

Implement `longestConsecutive(nums)` returning the length of the longest run of consecutive integers present in the array (order in the array does not matter). Aim for O(n) time.

Examples

Input: [100, 4, 200, 1, 3, 2]
Output: 4
The run 1, 2, 3, 4 has length 4.
Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
0 through 8 is a run of 9.

Sample tests

Input: longestConsecutive([100,4,200,1,3,2])
Output: 4
Input: longestConsecutive([0,3,7,2,5,8,4,6,0,1])
Output: 9

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Sorting first is O(n log n), not the required O(n).
  • Counting upward from every element (not just run starts) is O(n^2).

Learning resources

  • Wikipedia: Hash table
Approach & explanation (try first)

A set gives constant-time lookups. Each run is counted exactly once because counting only begins at a value with no predecessor in the set, so the inner while loop visits every element at most once overall. O(n) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.