[Leetcode] 128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

initial

Dafuq how do u solve this

I chatgpted and the logic is opposite of what I thought. We only want to do our main logic if that number is the very starting point (i.e. theres no number below that exists). For example if [100, 5,3,2], we wanna skip the logic and do it on 2 cuz it is starting point.

but this is still TLE

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        check = set(nums)
        ans = 0
        for num in nums:
            if num - 1 not in check:
                current_num = num
                count = 1
                while current_num + 1 in check:
                    current_num += 1
                    count += 1
                ans = max(ans, count)
        return ans

revisited aug 20th

i didnt know at all lol even after solving. the set way is easier

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans=0;
        Set<Integer> set = new HashSet<>();
        for(int num:nums) set.add(num);
        for(int num: set){
            if(!set.contains(num-1)){
                int tmp=1;
                int cur_num = num;
                while(set.contains(cur_num+1)){
                    tmp+=1;
                    cur_num+=1;
                }
                ans=Math.max(ans,tmp);
            }
        }
        return ans;
    }
}

solution

We use a hashmap isntead to avoid tle

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_map = {}
        res = 0
        for num in nums:
            if num not in num_map:
                left = num_map.get(num - 1, 0)
                right = num_map.get(num + 1, 0)
                total_length = left + right + 1

                res = max(res, total_length)

                num_map[num] = total_length
                num_map[num - left] = total_length
                num_map[num + right] = total_length
            else:
                continue
        return res

complexity

n time
n space