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;

m.reserve(nums.size());

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;

cur_streak++;

num++;

}

}

max_streak = max(max_streak, cur_streak);

}

return max_streak;

}

**Python**

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

visited.add(num)

cur_streak_right = 1

cur_num = num + 1

while cur_num in s and cur_num not in visited:

visited.add(cur_num)

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:

visited.add(cur_num)

cur_streak_left += 1

cur_num -= 1

max_streak = max(cur_streak_left + cur_streak_right, max_streak)

return max_streak

Last modified 4yr ago