[LC] 128. Longest Consecutive Sequence

[seungriyou]

<128. Longest Consecutive Sequence>

Approach

문제의 조건 중 time complexity 조건에 유의해야 한다.

You must write an algorithm that runs in O(n) time.

O(n) time에 동작하는 로직을 작성하려면, 주어진 nums를 순회하면서 consecutive elements 임을 O(1)에 알 수 있어야 한다!

그리고 O(1)에 lookup이 가능한 자료구조는 hash table이다.

또한, 중복되는 원소는 고려할 필요가 없으므로, 주어진 nums를 set(nums)로 변환하여 중복을 제거하자.

Idea 1: Union-Find

1 차이 나는 원소들을 합쳐나가려면 union-find가 가장 먼저 떠오른다. union-find 로직을 다음과 같이 설계할 수 있다.

• 현재 보고 있는 값 num과 1 차이 나는 값(num - 1, num + 1)을 발견하면 union
• num - 1, num + 1이 존재하는지 O(1)에 찾기 위해 hash table num_idx 유지
• union 할때마다 length 값 업데이트 (length가 긴 쪽으로 모으도록 함)

Caution

union-find의 find 및 union 연산의 시간 복잡도는 경로 압축 & 랭크 기반 합치기를 통해 거의 상수 시간(O(1)) 으로 간주할 수 있다.

ref: https://wikidocs.net/178971

nums가 비어있을 때는 빠르게 0을 반환한다.

# early stop
if not nums:
    return 0

union-find에서 필요한 함수는 다음과 같이 작성한다. 이때, union_parent의 경우는 length가 긴 쪽으로 union 하도록 한다.

# for union-find
parent = [i for i in range(n)]
length = [1] * n
# for hash table (O(1) lookup)
num_idx = {}

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    # a, b의 parent 찾기
    a_parent, b_parent = find_parent(a), find_parent(b)

    # a와 b의 parent가 다르다면, length가 긴 쪽으로 모으도록 함
    if a_parent != b_parent:
        if length[a_parent] < length[b_parent]:
            parent[a_parent] = parent[b_parent]
            length[b_parent] += length[a_parent]
        else:
            parent[b_parent] = parent[a_parent]
            length[a_parent] += length[b_parent]

중복을 제거한 nums를 순회하며, num - 1, num + 1이 존재한다면 union 해나가는 방식으로 length를 업데이트 해나간다.

# remove duplicate w/ set
for i, num in enumerate(set(nums)):
    # hash table에 저장
    num_idx[num] = i

    # num - 1, num + 1이 존재한다면 union
    if (left := num - 1) in num_idx:
        union_parent(i, num_idx[left])
    if (right := num + 1) in num_idx:
        union_parent(i, num_idx[right])

return max(length)

Idea 2: Simple Traversal

hash table을 이용해 num - 1, num + 1을 O(1)에 찾는 점에 유의하면 union-find를 활용할 필요 없이 단순 반복문만으로 로직을 작성할 수 있다.

consecutive sequence의 길이를 구하는 것이므로 two-pointer의 개념도 사용 가능하다!

이 로직의 핵심은 다음과 같다.

1. nums를 순회하며 현재 보고 있는 num에 대해 left = num - 1와 right = num + 1가 hash table에 있는지 확인한다.

2. 그리고 left와 right에서 각각 1씩 빼거나 더해가며 two pointer를 양옆으로 확장하듯이 hash table에서 삭제해나간다.

   모든 숫자가 한번만 _set에서 제거되기 때문에, 전체적으로 while 루프는 각 숫자에 대해 최대 O(1)만큼의 연산이 추가로 발생

3. 더이상 left & right와 연속된 값이 없다면 right - left - 1 값을 현재의 res 값과 비교해 업데이트 한다.

4. hash table에 더이상 원소가 없다면 종료한다.

if not nums:
    return 0

# hash table for O(1) lookup
_set = set(nums)
# max length of consecutive sequence
res = 0

for num in nums:
    # num의 양 옆 값 구하기
    left, right = num - 1, num + 1

    # left 및 right가 _set에 존재할 때까지 삭제 & 확장
    while left in _set:
        _set.remove(left)
        left -= 1
    while right in _set:
        _set.remove(right)
        right += 1
    
    # res 값 업데이트
    res = max(res, right - left - 1)

    # hash table이 비었다면 더 이상 확인할 필요가 없으므로 종료
    if not _set:
        break

return res

Complexity

• Time: O(n)
• Space: O(n)