Longest Consecutive Sequence

Medium· hash set

Problem

Given an unsorted array of integers, return the length of the longest run of consecutive integer values that can be formed from its elements. The elements do not need to be adjacent in the array, and the algorithm should run in O(n) time.

Examples

Input: nums = [100,4,200,1,3,2]

Output: 4

The values 1, 2, 3, 4 form the longest consecutive run.

Input: nums = [9,1,4,7,3,-1,0,5,8,-1,6]

Output: 7

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Hints & approach

Hint 1

Sorting solves it in O(n log n). How can a set help avoid that?

Hint 2

Only start counting from a number that is the beginning of a run.

Hint 3

x starts a run exactly when x - 1 is not in the set.

Approachtry the hints first

Put every number into a hash set. For each value x in the set, skip it if x - 1 is also present, because then x is not the start of a run. Otherwise count upward x + 1, x + 2, ... while they are in the set, and update the best length. Each number is visited by at most one upward walk, so the total work is linear.

Time O(n) · Space O(n)

← PreviousGroup Anagrams Next →Insert Delete GetRandom O(1)