128.longest-consecutive-sequence.md

128. Longest Consecutive Sequence

This problem is looking for "consecutive", not only "increasing", so we don't use the approach of 300. Longest Increasing Subsequence.

Brute Force

We can iterate all element x, then iterate descendingly (x - 1, x - 2, ...) and ascendingly (x + 1, x + 2, ...) to check if the number exist in our array. What is the optimal way to check if a number exist in our array? We can use hash set to store all numbers in our array, then we can check if a number exist in O(1) time.

def longestConsecutive(self, nums: List[int]) -> int:
    nums_set = set(nums)
    result = 0
    for i in range(len(nums)):
        length = 1
        left = nums[i] - 1
        while left in nums_set:
            length += 1
            left -= 1
        right = nums[i] + 1
        while right in nums_set:
            length += 1
            right += 1
        result = max(result, length)
    return result

fun longestConsecutive(nums: IntArray): Int {
    val set = HashSet<Int>()
    for (num in nums) set.add(num)

    var result = 0
    for (num in nums) {
        var count = 1
        var current = num - 1
        // Check decreasing sequence
        while (set.contains(current)) {
            current--
            count++
        }
        // Check increasing sequence
        current = num + 1
        while (set.contains(current)) {
            current++
            count++
        }
        result = max(result, count)
    }
    return result
}

• Time Complexity: O(n^2).
• Space Complexity: O(n).

Hash Table

We can optimize the brute force approach, there is duplicate check when checking descending and ascendingly. For example, the input array [3, 1, 2], then the consective sequence will be 1, 2, 3, then it will duplicate check for starting from 1 then check asencdingly and starting from 3 then check descendingly.

input = [3, 1, 2]

// For the checking sequence, it will be double check from 1 to 3 and 3 to 1.
1, 2, 3
*->
    <-*

The number 2 will be checked twice when we check 1 ascendingly and check 3 descendingly.

To avoid this, we check only in either ascendingly or descendingly direction, here we choose iterate ascendingly x + 1, x + 2, ... direction only, we choose every element as the start of the consective sequence. We can avoid checking descendingly by checking if x - 1 does not exist in the input.

def longestConsecutive(self, nums: List[int]) -> int:
    nums_set = set(nums)
    result = 0
    for i in range(0, len(nums)):
        n = nums[i]
        if n - 1 not in nums_set:
            while n in nums_set:
                n += 1
            result = max(result, n - nums[i])
    return result

fun longestConsecutive(nums: IntArray): Int {
    val hashSet = hashSetOf<Int>()
    for (num in nums) {
        hashSet.add(num)
    }

    var maxStreak = 0
    for (i in 0 until nums.size) {
        val num = nums[i]
        // This is the key, we only check ascending direction.
        // We're looking for the start sequence and it has not "left number" (num - 1)

        // If we have num - 1 which is consecutive to num, answer will check at num - 1 iteration, not current iteration.
        if (!hashSet.contains(num - 1)) {
            var next = num + 1
            var length = 1
            while (hashSet.contains(next)) {
                next++
                length++
            }
            maxStreak = max(maxStreak, length)
        }
    }
    return maxStreak
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Or we still can check ascendingly and desencdingly, but we just remove the number from set when we check it, so we can avoid duplicate check.

def longestConsecutive(self, nums: List[int]) -> int:
    nums_set = set(nums)
    result = 0
    for i in range(0, len(nums)):
        n = nums[i] - 1
        streak = 1
        while n in nums_set:
            nums_set.remove(n)
            streak += 1
            n -= 1
        
        n = nums[i] + 1
        while n in nums_set:
            nums_set.remove(n)
            streak += 1
            n += 1
        
        result = max(result, streak)
    return result

fun longestConsecutive(nums: IntArray): Int {
    val hashSet = hashSetOf<Int>()
    for (num in nums) {
        hashSet.add(num)
    }

    var maxStreak = 0
    for (i in 0 until nums.size) {
        var currentStreak = 1

        // Check ascendingly
        num = nums[i] + 1
        while (hashSet.contains(num)) {
            hashSet.remove(num)
            currentStreak++
            num++
        }

        // Check descendingly
        var num = nums[i] - 1
        while (hashSet.contains(num)) {
            hashSet.remove(num)
            currentStreak++
            num--
        }
        maxStreak = maxOf(maxStreak, currentStreak)
    }
    return maxStreak
}

• Time Complexity: O(n).
• Space Complexity: O(n).