Longest Consecutive Sequence

Medium · Arrays & Hashing

Given an unsorted array of integers, find the length of the longest sequence of consecutive integers (numbers that follow each other with a difference of exactly 1) that can be formed using elements from the array. The elements of the sequence do not need to be contiguous in the original array. You should aim for an algorithm that runs in O(n) time, so sorting the array is not the intended approach.

Examples

Input:  nums = [100,4,200,1,3,2]
Output: 4
Why:    The longest run of consecutive numbers is [1,2,3,4], which has length 4.

Input:  nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Why:    The longest run is [0,1,2,3,4,5,6,7,8], length 9.

Input:  nums = []
Output: 0

Constraints

0 <= nums.length <= 10^5; -10^9 <= nums[i] <= 10^9; the algorithm should run in O(n) time

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Consecutive Sequence

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Consecutive Sequence. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.