128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

My Answer 1: Accepted (Runtime: 64 ms - 32.59% / Memory Usage: 14.9 MB - 99.83%)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        nums.sort()
        result = 1
        temp = 1
        
        for i in range(len(nums)-1):
            print(nums[i])
            if nums[i] + 1 == nums[i+1]:
                temp += 1
            elif nums[i] == nums[i+1]:
                continue
            else:
                result = max(result, temp)
                temp = 1
        
        result = max(result, temp)
        
        return result

nums 를 sort 한 후 연속된 숫자 찾는 식으로 함..
연속되면 temp+1 같으면 continue 다르면 result 에 max 값으로 업데이트

Time complexity : O(nlgn). Space complexity : O(1) (or O(n)).

Approach 3: HashSet and Intelligent Sequence Building

Solution 1: Runtime: 84 ms - 19.74% / Memory Usage: 15.3 MB - 53.91%

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        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

nums 를 set 로 만들어서
num - 1 값이 set 에 없으면 시작값으로 잡고 +1 값들의 개수를 셈
longest_streak 는 최댓값으로 업데이트