Leetcode: Longest Consecutive Sequence

This question is mainly asked at Google, Microsoft, and Amazon. It is as follows:

Given an unsorted array of integers num, return the length of the longest consecutive elements sequence. We can either do a brute force or sorting algorithm to attempt to solve this problem. We try to see if an array contains a number, and solve it in that manner. It is relatively simple in Python. We first define the longest streak to be 0 and iterate through all of the numbers inside. It sees if the consecutive numbers are in nums and then adds to the current streak if that is there. It goest through all the numbers first. 

class Solution:

    def longestConsecutive(self, nums):

        longest_streak = 0

        for num in nums:

            current_num = num

            current_streak = 1

            while current_num + 1 in nums:

                current_num += 1

                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

          return longest_streak

However, this takes cubic time, and results in a time limit exceeded.

The other way that we can do this is by HashSet and Intelligent Sequence Building. The brute force is a right track but it's missing a few optimizations to reach O(n) time complexity. This time though, we store the numbers in a HashSet. 

class Solution:

    def longestConsecutive(self, nums):

        longest_streak = 0

        num_set = set(nums)

        for num in num_set:

            if num - 1 not in num_set:

                current_num = num

                current_streak = 1

                while current_num + 1 in num_set:

                    current_num += 1

                    current_streak += 1

            longest_streak = max(longest_streak, current_streak)

        return longest_streak 

So again, it checks all the numbers in the set and then set the current streak to 1 then, and it ONLY goest for numbers not in the particular set.