Comment on page

128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
The Idea: First we store all the numbers into a hash table. We'll use this table to jump around finding consecutive numbers. To avoid making this N^2, we need to impose some rules on how will jump from one integer from the next. The process goes as follows. For each number of the array, we attempt to follow a streak. I've arbitrarily decided to look up acending sequences. I can identify the start of a streak when there exists a number + 1 of the present number, and their doesnt exist a smaller number - 1 than the present number. If these conditions hold true, then I know that I've identified the smallest number of a potentially long steak. Now, I can iterate through this streak by identifing num + 1 through the hash table. As I do, I mark said value as visited. This is to ensure that I dont try to and reidentify the loop (as visited indicates that the streak was already identified as part of another streak that was already counted). So iterating through this streak, I mark the integers visited, and increment the streak length. At the end of the streak, I update the maximum streak, and until all streaks are identified in the sequence.
Complexity: O(2n) time and O(n) space
int longestConsecutive(vector<int>& nums) {
unordered_map<int, bool> m;
for (int num : nums)
m[num] = false;
int max_streak = 0;
for (int num : nums) {
int cur_streak = 1;
if (m.find(num + 1) != m.end() && !m[num + 1] &&
m.find(num-1) == m.end()) {
while (m.find(num + 1) != m.end() && !m[num + 1]) {
m[num] = true;
max_streak = max(max_streak, cur_streak);
return max_streak;
The idea is the same. For every number, count the number of ascending elements in front of it, as well as descending elements behind it. These numbers are to be a part of a single streak. For every streak, we record and maintain the maximum length. Each element in the list will be visited once and be identified as part of a unique streak, so the complexity is linear.
class Solution:
def longestConsecutive(self, nums):
:type nums: List[int]
:rtype: int
s = set(nums)
max_streak = 0
visited = set()
for num in nums:
# find the longest streak to the right
cur_streak_right = 1
cur_num = num + 1
while cur_num in s and cur_num not in visited:
cur_streak_right += 1
cur_num += 1
# find the longest streak to the left
cur_streak_left = 0
cur_num = num - 1
while cur_num in s and cur_num not in visited:
cur_streak_left += 1
cur_num -= 1
max_streak = max(cur_streak_left + cur_streak_right, max_streak)
return max_streak