128. Longest Consecutive Sequence

Problem Link

Brute Force: Since we only need to find the longest consecutive sequence irrespective of order in array, we can check the sequence starting each element and take the longest. This would result in \(O(n^2)\) time complexity.

To optimize this, we can just check the sequence for \(num_i\) whose previous number (\(num_i-1\)) isn't present in our array, as these number are guaranteed to generate unique sequence . This would result in checking the sequence for elements only once.

Pseudocode

• Iterate over the nums array. To keep checks constant time, we can also create a Hashset out of nums array.
• For each num, if the previous (num-1) isn't present in our array means we've a unique sequence starting from this num.
• To generate this sequence, declare a length pointer and increment it until we exhaust the sequence numbers present in our hashset.
• Finally use a global variable to maintain the maximum length.

Runtime Complexity

Time: \(O(n)\), single iteration over each element with constant time checks. It might look like we're iterating within 2 loops, but the conditional will reduce the inner iteration such that we're not repeating checks.

Space: \(O(n)\) <- from hashmap.

PythonGo

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        nums = set(nums)
        for num in nums:
            if num-1 not in nums:
                length = 1
                while num+length in nums:
                    length+=1
                res = max(length, res)
        return res

func longestConsecutive(nums []int) int {
    set := make(map[int]struct{})
    for _, num := range nums {
        set[num] = struct{}{}
    }
    res := 0
    for num, _ := range set {
        if _, ok := set[num-1]; !ok {
            length := 1
            for {
                if _, ok := set[num+length]; ok {
                    length++
                } else {
                    break
                }
            }
            res = max(res, length)
        }
    }
    return res
}

---