Logo

dev-resources.site

for different kinds of informations.

Longest Consecutive Sequence

Published at
4/20/2022
Categories
leetcode
array
blind75
Author
Stylus07
Categories
3 categories in total
leetcode
open
array
open
blind75
open
Longest Consecutive Sequence

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.

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.
var longestConsecutive = function (nums) {
    let num_set = new Set(nums);
    let longestStreak = 0;
    for (let num of nums) {
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;
            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }
    return longestStreak;
}

Time Complexity : O(n)

Featured ones: