Longest Consecutive Sequence

How it works

When we place a new number into the map, it may connect two existing sequences or extend one of them. Instead of scanning forward or backward, we only look at the lengths stored at the neighbors:

• mp[num - 1] gives the length of the sequence ending right before num
• mp[num + 1] gives the length of the sequence starting right after num

By adding these together and including the current number, we know the total length of the new merged sequence. We then update the left boundary and right boundary of this sequence so the correct length can be retrieved later. This keeps the whole operation very efficient and avoids repeated work.

Steps

1. Create a hash map mp that stores sequence lengths at boundary positions.
2. Initialize res = 0 to store the longest sequence found.
3. For each number num in the input:
   • If num is already in mp, skip it.
   • Compute the new sequence length:
     • length = mp[num - 1] + mp[num + 1] + 1
   • Store this length at num.
   • Update the boundaries:
     • Left boundary: mp[num - mp[num - 1]] = length
     • Right boundary: mp[num + mp[num + 1]] = length
   • Update res to keep track of the longest sequence.
4. Return res after processing all numbers.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Starting a Sequence from Every Number

A common inefficiency is to start counting a sequence from every number in the array, which leads to O(n^2) time complexity. The key optimization is to only start counting from numbers that are the beginning of a sequence (i.e., num - 1 is not in the set).

Not Handling Duplicates Properly

The input array may contain duplicate values. Using a set automatically handles this, but if you iterate over the original array instead of the set, you may process the same sequence multiple times, wasting computation.

Forgetting to Handle Empty Input

When the input array is empty, the longest consecutive sequence has length 0. Some implementations that assume at least one element exists may fail or return incorrect results for this edge case.

from typing import List
from collections import defaultdict

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        mp = defaultdict(int)
        res = 0

        for num in nums:
            if not mp[num]:
                mp[num] = mp[num - 1] + mp[num + 1] + 1
                mp[num - mp[num - 1]] = mp[num]
                mp[num + mp[num + 1]] = mp[num]
                res = max(res, mp[num])
        return res

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> mp;
        int res = 0;

        for (int num : nums) {
            if (!mp[num]) {
                mp[num] = mp[num - 1] + mp[num + 1] + 1;
                mp[num - mp[num - 1]] = mp[num];
                mp[num + mp[num + 1]] = mp[num];
                res = max(res, mp[num]);
            }
        }
        return res;
    }
};