Blind 75.31 - Longest Consecutive Sequence

Longest consecutive sequence.

Problem description

Taken directly from LeetCode.

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

Constraints:

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

Solution type

Caching.

Solution

Topological sort would work if you imagine edges between consecutive numbers, but if you have edges between consecutive numbers then the problem is basically solved for you already. The hard part is deriving those “edges” somehow.

The \(O(n)\) limitation is weird because most graph algorithms are a function of both $$

V

\(and\)

E

$$. I think this implies that we should be thinking about the construction of the graph rather than necessarily applying a traditional graph algorithm.

The way that stands out to me thinking about this right now is to create an unordered map from our input, where each value in nums is a key¹. The value of each key is initialized to -1; we then go through nums again, and if we find that the key value minus one is in the unordered map as a key, then we write key value minus one to the value of the key. We do three \(O(n)\) operations which keeps our runtime at \(O(n)\) overall. It’s a little clunky but I think it works.

Oops, was writing in C++ when I meant to switch off to Python. Here’s what I had before switching…

int longestConsecutive(vector<int>& nums) {
    unordered_map<int, pair<int, int>> m;
    for (int num : nums) {
        m[num] = pair<int,int>(INT_MIN, INT_MIN);
    }
    for (int num: nums) {
        if (m.find(num - 1) != m.end()) {
            m[num].first = num - 1;
            m[num - 1].second = num; 
        }
    }
    int longest = 1;
    for (int num: nums) {
        stack<int> dfs;
        dfs.push(num);
        while (!dfs.empty()) {
            
        }
    }
    return longest;
}

I missed a cheeky empty list test case but otherwise got a right answer pretty smoothly. I think the dictionary in my solution can be argued to be a very weird-looking adjlist or adjacency matrix, where the starting vertex is based on the key and the only “edges” possible are to num - 1 and num + 1. From there, I just apply DFS.

 def longestConsecutive(self, nums: List[int]) -> int:
    m = {}
    for num in nums:
        m[num] = [False, False]
    for num in nums:
        if num - 1 in m.keys():
            m[num][0] = True
            m[num - 1][1] = True
    longest = 0
    for num in nums:
        dfs = []
        dfs.append(num)
        currentLength = 0
        while len(dfs):
            current = dfs[-1]
            dfs.pop(-1)
            if m[current][0]:
                dfs.append(current - 1)
                m[current][0] = False
                m[current - 1][1] = False
            if m[current][1]:
                dfs.append(current + 1)
                m[current][1] = False
                m[current + 1][0] = False
            currentLength += 1
        longest = max(longest, currentLength)
    return longest

There are some weird online solutions that just…don’t seem right? There are, however, proper ways to do the “DFS” without creating a stack and using a set instead of a hash map; the idea is that since you always know what values your adjacent nodes will be, you can replace True / False checks with lookup in a set. Overwriting True with False can be replaced with set removal. Removing the DFS data structure is a little trickier conceptually, but since you know that you can only ever go one of two directions and you will always be going in one of two directions in your search (i.e. you never go from looking for decreasing values to looking for increasing values), you can use two variables instead. See below:

def longestConsecutive(self, nums: List[int]) -> int:
    s = set(nums)
    longest = 0
    for num in nums:
        decreasing = num - 1
        increasing = num + 1
        currentLength = 1
        while decreasing in s:
            s.remove(decreasing)
            decreasing -= 1
            currentLength += 1
        while increasing in s:
            s.remove(increasing)
            increasing += 1
            currentLength += 1
        longest = max(longest, currentLength)
    return longest

Fun fact: this is around where I stopped when I was grinding LeetCode for internships in 2021. I had to stop to focus on exam stuff, and I thankfully managed to land a very good internship without having done the whole grind. I didn’t solve this problem back then; I’m happy to see I’ve improved on my previous self, at least for this one problem.

1. We don’t care about duplicates because having duplicates does not affect the length of the longest consecutive subsequence, although if we included duplicates it would make the problem only a little more annoying to implement - you’d want to do a pair type value that contains count and previous in a tuple. ↩