hashing · Problem 4 of 5
Longest Consecutive Sequence
medium
Google
Meta
Amazon
Microsoft
Spotify
GoogleMetaAmazonMicrosoftSpotifyGiven an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time complexity.
longestConsecutive([100, 4, 200, 1, 3, 2]) -> 4
// The longest consecutive elements sequence is [1, 2, 3, 4]. Its length is 4.
longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) -> 9
longestConsecutive([]) -> 0Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| longestConsecutive([100,4,200,1,3,2]) | standard unsorted list | 4 | — |
| longestConsecutive([0,3,7,2,5,8,4,6,0,1]) | large sequence with duplicates | 9 | — |
| longestConsecutive([42]) | single element | 1 | — |
| longestConsecutive([]) | empty array | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(n)
Although the while loop is nested, each number is visited at most twice (once in the outer set iteration, once in the streak counting loop), guaranteeing strict O(n) runtime.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left