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
