Solution: Longest Consecutive Sequence

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #128 (Medium): Longest Consecutive Sequence

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

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 <= 10^5
• -10^9 <= nums[i] <= 10^9

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In order to accomplish this task in O(N) time, we'll have to have some way of looking up values (nmap), which means a set or map object. We'll also need some way of keeping track of which numbers have already been seen.

(Note: We could forego the seen data structure entirely and just follow each path to its end every time, but that would cause us to redo the same sections over and over again, pushing the time complexity to O(N^2).)

If we use a set for nmap, then we would need to use a map for seen in order to be able to look the numbers up by value. If we instead use a map for nmap, with each number pointing to its index, then we can instead use those indexes with an array for seen, which will be more efficient.

(Note: Since we'll be iterating through nums from front to back in the next section, we should make sure that we store only the first index at which a number is found in nmap. Later indexes of duplicate numbers can be ignored, as by then the number will already be considered seen.)

But now we run into the issue of potentially finding the middle of a sequence before we find the beginning of the sequence. For this we can take inspiration from a union-find approach and/or dynamic programming (DP) approach; We can use seen to store the length of the sequence found when starting at the given number.

(Note: We don't need to store path length data in any but the smallest number of a found chain, as those nodes can never be actively visited again. Only the entry point, which is the smallest number, needs to have the accurate path length stored. For the other numbers, we just have to register them as seen, so we can just fill them with a 1 or any non-zero number to make the check easy.)

Then, if we later find an earlier number in the same sequence, we can notice the value stored in seen when we link up with an already-visited tail end of the same sequence and just add that value (representing the tail's length) to our count of numbers.

For example, consider nums = [4,5,6,1,2,3,0]. We start at 4, then track through 5 and 6, filling the seen indexes corresponding to 5 and 6 with a 1 each (seen[1] = 1, seen[2] = 1). Once we reach the end of that chain and have a count of 3, we store that 3 in the seen index corresponding to 4 (seen[0] = 3).

Then, because we've seen 5 and 6 while checking 4, we skip to 1. At 1, we track through 2 and 3, filling them with 1s (seen[4] = 1, seen[5] = 1). After that, we run into 4, which has a value of 3 stored in seen. At this point, count is 3 (from numbers 1, 2, and 3), but we've just run into another already-discovered chain of 3 (numbers 4, 5, and 6), so we can fill the seen index corresponding to 1 with a 6 (seen[3] = 6).

Then we skip past 2 and 3, and the 0 will lead us back to 1, so we'll have a result of 7 for the seen index corresponding to 0 (seen[6] = 7).

At each step, when we're about to store the count in seen, we can also update our best result so far (ans). Then, once we've reached the end of the iteration, we can just return ans.

• Time Complexity: O(N) where N is the length of nums
• Space Complexity: O(N) for nmap and seen

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var longestConsecutive = function(nums) {
    let nmap = new Map(), ans = 0,
        seen = new Uint32Array(nums.length)
    for (let i = 0; i < nums.length; i++)
        if (!nmap.has(nums[i])) nmap.set(nums[i], i)
    for (let n of nums) {
        let curr = n, count = 1
        if (seen[nmap.get(curr)]) continue
        while (nmap.has(curr+1)) {
            let ix = nmap.get(++curr)
            if (seen[ix]) {
                count += seen[ix]
                break
            } else seen[ix] = 1, count++
        }
        seen[nmap.get(n)] = count
        ans = Math.max(ans, count)
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nmap, seen, ans = defaultdict(int), [0] * len(nums), 0
        for i in range(len(nums)):
            if nums[i] not in nmap: nmap[nums[i]] = i
        for n in nums:
            curr, count = n, 1
            if seen[nmap[n]]: continue
            while curr+1 in nmap:
                curr += 1
                ix = nmap[curr]
                if seen[ix]:
                    count += seen[ix]
                    break
                else:
                    seen[ix] = 1
                    count += 1
            seen[nmap[n]], ans = count, max(ans, count)
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> nmap = new HashMap<>();
        int ans = 0;
        int[] seen = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            if (!nmap.containsKey(nums[i])) nmap.put(nums[i], i);
        for (int n : nums) {
            int curr = n, count = 1;
            if (seen[nmap.get(curr)] > 0) continue;
            while (nmap.containsKey(curr+1)) {
                int ix = nmap.get(++curr);
                if (seen[ix] > 0) {
                    count += seen[ix];
                    break;
                } else {
                    seen[ix] = 1;
                    count++;
                }
            }
            seen[nmap.get(n)] = count;
            ans = Math.max(ans, count);
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> nmap;
        int ans = 0;
        vector<int> seen(nums.size());
        for (int i = 0; i < nums.size(); i++)
            if (nmap.find(nums[i]) == nmap.end())
                nmap[nums[i]] = i;
        for (auto& n : nums) {
            int curr = n, count = 1;
            if (seen[nmap[curr]]) continue;
            while (nmap.find(curr+1) != nmap.end()) {
                int ix = nmap[++curr];
                if (seen[ix]) {
                    count += seen[ix];
                    break;
                } else seen[ix] = 1, count++;
            }
            seen[nmap[n]] = count;
            ans = max(ans, count);
        }
        return ans;
    }
};