17. Longest Consecutive Sequence

Link to the problem

Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]

Return 4.

Idea

Maintain a dictionary left/right with number as key, and maximum segment length on its left/right as the value. Each time a new element is inserted, we can maintain the corresponding values for endpoints only.

Solution

class Solution {
public:
    int longestConsecutive(vector<int> &nums) {
        unordered_map<int, int> left, right;
        for (auto it = nums.begin(); it != nums.end(); it++) {
            if (left.find(*it) != left.end()) continue;
            bool has_left = (left.find(*it - 1) != left.end());
            bool has_right = (right.find(*it + 1) != right.end());
            if (!has_left && !has_right) {
                left[*it] = 1;
                right[*it] = 1;
            } else if (!has_left && has_right) {
                left[*it] = 1;
                int tot = 1 + right[*it + 1];
                right[*it] = tot;
                left[*it + right[*it + 1]] = tot;
            } else if (has_left && !has_right) {
                right[*it] = 1;
                int tot = 1 + left[*it - 1];
                left[*it] = tot;
                right[*it - left[*it - 1]] = tot;
            } else {
                left[*it] = 1 + left[*it - 1];
                right[*it] = 1 + right[*it + 1];
                int tot = 1 + left[*it - 1] + right[*it + 1];
                left[*it + right[*it + 1]] = tot;
                right[*it - left[*it - 1]] = tot;
            }
        }
        int rtn = 0;
        for (auto it = left.begin(); it != left.end(); it++) {
            rtn = max(rtn, it->second);
        }
        return rtn;
    }
};

68 / 68 test cases passed.
Runtime: 13 ms