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

Last updated