Longest Consecutive Sequence

Leetcode Problem 128: Longest Consecutive Sequence

Problem Summary

Given an unsorted array of integers, return the length of the longest consecutive elements sequence (e.g., [100, 4, 200, 1, 3, 2] → longest sequence [1, 2, 3, 4] → length 4).

Your solution must run in O(n) time.

Constraints:

• The array has between 0 and 100,000 elements.
• Each element is a 32-bit signed integer.

Techniques

• Array
• Hash Table
• Union-Find

Solution

function longestConsecutive(nums: number[]): number {
    let numbers = new Set<number>(nums)
    let count = 0
    let maxCount = 0

    for(let num of numbers.values()) {
        if (!numbers.has(num - 1)) {
            let current = num
            count = 1
            
            while (numbers.has(current + 1)) {
                current++
                count++
            }

            maxCount = Math.max(maxCount, count)
        }
    }

    return maxCount
};

console.log(longestConsecutive([100,4,200,1,3,2]))