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