Longest Consecutive Sequence

Medium~25 min

Given 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.

A consecutive sequence is a sequence of numbers where each number is exactly 1 more than the previous number (e.g., [1, 2, 3, 4]).

Examples

Example 1
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Its length is 4.
Example 2
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Its length is 9.
Example 3
Input: nums = []
Output: 0
Explanation: Empty array has no consecutive sequence.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • Expected time complexity: O(n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run