128. Longest Consecutive Sequence

[zeikar]

Problem link

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

Problem Summary

배열이 주어질 때 가장 긴 원소들의 연속 증가 길이를 구하는 문제 (순서는 상관 없음)

Solution

O(n log n) 풀이는 정렬하면 되니까 쉽다. **O(n)**은 약간 생각해야 함.
일단 O(n)이니까 hashmap 방식으로 가야하고 hashmap으로 구현하려면 각 원소들을 한 번씩만 순회해야 한다.

원소들을 set에 넣어두고 set의 처음 지점인 원소부터 쭉 올라가면서 길이를 재주면 된다.

처음에는 dict에 넣고 배열을 순회하면서 처음인지 판단했는데 이럴 경우 visited가 추가로 필요하다. 순회 자체도 set에서부터 하는 것이 편함!

Source Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        answer = 0
        
        for n in s:
            if n-1 in s:
                continue
            
            l = 0
            next = n
            while next in s:
                l += 1
                next += 1
            answer = max(answer, l)

        return answer