목차

Longest Consecutive Sequence

ps
링크leetcode.com/…
출처LeetCode
문제 번호128
문제명Longest Consecutive Sequence
레벨Medium
분류

기본

시간복잡도O(n)
인풋사이즈n<=10^5
사용한 언어python 3.14
제출기록36.68MB / 53ms
최고기록0ms
해결날짜2026/05/16

풀이

코드

정해 O(n)

problems/leetcode/q0128.py
"""Solution code for "LeetCode 128. Longest Consecutive Sequence".

- Problem link: https://leetcode.com/problems/longest-consecutive-sequence
- Solution link: http://www.teferi.net/ps/problems/leetcode/128
"""

from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        inf = max(nums) + 2
        num_set = set(nums)
        answer = 0
        for x in num_set:
            if x - 1 in num_set:
                continue
            length = next(i for i in range(x, inf) if i not in num_set) - x
            answer = max(answer, length)
        return answer

정렬 기반 - O(nlogn)

problems/leetcode/q0128_sort.py
"""Solution code for "LeetCode 128. Longest Consecutive Sequence".

- Problem link: https://leetcode.com/problems/longest-consecutive-sequence
- Solution link: http://www.teferi.net/ps/problems/leetcode/128
"""

import collections
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        return max(
            collections.Counter(
                x - i for i, x in enumerate(sorted(set(nums)))
            ).values(),
            default=0,
        )