128. Longest Consecutive Sequence

Problem

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

Example 3:

Input: nums = [1,0,1,2] Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Approaches

1. Brute Force
2. Sorting and Single Loop
3. Hash Table

Brute Force

The idea is to loop through each number and check if the next number exists. If the next number exists increase the current streak or else update the result streak to current streak and reset current streak to 0 and start looping through the array.

The Problem with this approach is Time Complexity of O(n^2)

function longestConsecutive(nums: number[]): number {
    let result = 0
 
    // This will remove duplicates in the array
    const store = new Set(nums)
 
    // Loop through each num in the array
    for (let num of nums) {
        let currentStreak = 0
        let currentNum = num
 
        while(store.has(currentNum)) {
            currentNum++
            currentStreak++
        }
 
        result = Math.max(result, currentStreak)
    }
 
    return result
}

Sorting and Single Loop

The idea here is to sort the array with O(n log n) and then iterate over the array. While iterating if the current and previous number is same go to next position and check if both are not same and previous one is less than 1 to current. If so increment currentstreak or else break the current streak and update result with current streak. Start the current streak with 1 again

function longestConsecutive(nums: number[]): number {
    if(nums.length === 0) {
        return 0
    }
 
    // Sort nums array
    nums.sort((a, b) => a - b)
 
    // Initialize Variable
    let longestLength = 1
    let currentLength = 1
 
    // Loop Through array
    for (let i = 1; i < nums.length; i++) {
        if(nums[i] !== nums[i - 1]) {
            // if numbers are consecutive increment
            if(nums[i] === nums[i -1] + 1) {
                currentLength++
            } else {
                longestLength = Math.max(longestLength, currentLength)
                longestLength = 1
            }
        }
    }
 
    return Math.max(longestLength, currentLength)
}

Hash Table Approach

The approach is to store all the values in a set, so search would be O(1).

There are two types of numbers in the sequence

Type 1: The number is start of the sequence Type 2: The number is part of the sequence

We need to find the number that is start of the sequence and increment until there is no sequence

function longestConsecutive(nums: number[]): number {
    const set = new set(nums)
 
    let longestLength = 0
 
    for (let num of set) {
        // if set doesn't have previous num sequence this is where we start
        if (!set.has(num -1)) {
            let currentLength = 0
            while(set.has(num + currentLength)) {
                currentLength++
            }
            longestLength = Math.max(currentLength, longestLength)
        }
    }
    return longestLength
}