Longest Consecutive Sequence

Problem

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in O(n) time.

Examples

Example 1:

Input: nums = [2,20,4,10,3,4,5]

Output: 4

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Constraints

• 0 <= nums.length <= 1000
• -10^9 <= nums[i] <= 10^9

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

Solution

For every number, we track what is the longest sequence it is a part of. For every number we read for the first time, we set its sequence length to the entry on the left + the entry on the right + 1. If those were empty, then its defaults to 0. We then need to update the endpoint of the new sequence we just made.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // Idea is to have a map track the current length the number is a part of
        //   If we add an unseen number, the length of the sequence its now is in the lengths 
        //   of the left-right side added plus itself (+1). We then need to update the endpoints,
        //   which we can find by walking left by the amount the left item thinks its length is, 
        //   and same with the right. Because we are only filling in unseen items, we can ignore 
        //   the fact that the items in the middle no longer have the correct length representation,
        //   because when an item is added, its always beside an existing endpoint(s).
        std::unordered_map<int, int> lengths;
        int result = 0;
        for (const auto &num : nums) {
            // We cant use contains here because accessing left/right will default insert 0,
            // what we really need to check is if the value is non-zero
            if (lengths[num] == 0) {
                const auto length = lengths[num-1] + lengths[num+1] + 1;
                lengths[num] = length;
                lengths[num - lengths[num-1]] = length;
                lengths[num + lengths[num+1]] = length;
                result = std::max(result, length);
            }
        }
        return result;
    }
};