128. Longest Consecutive Sequence

Problem

Tags: Array, Hash Table, Union Find

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

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

Constraints:

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

Code

JS

// 128. Longest Consecutive Sequence (10/2/53399)
// Runtime: 100 ms (82.57%) Memory: 47.41 MB (93.94%) 

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
	let max = 0;
	const nums_set = new Set(nums);

	for(let num of nums_set) {
		if(nums_set.has(num-1)) continue;
        
        let count = 1;
        while(nums_set.has(++num)) count++;
        
        max = count > max ? count : max;
    }

	return max;
};