Leetcode 회고 3.16-3.22

Source: Dev.to

Weekly Reflection (LeetCode)

“I realize it’s too clumsy to post for every LeetCode problem I solved, so I’ll accumulate a week’s reflections together and post them once.” – Di

1️⃣ Happy Number

Problem statement – If we repeatedly replace a number by the sum of the squares of its digits and eventually reach 1, the original number is called a happy number.
The difficulty is knowing when to stop the process if 1 never appears.

Mathematics behind the termination

Cycle‑detection implementation

seen = set()
while n != 1 and n not in seen:
    seen.add(n)
    nxt = 0
    while n:
        digit = n % 10
        nxt += digit * digit          # pow(digit, 2) is slower
        n //= 10
    n = nxt
return n == 1

The idea of using a set to detect duplicates comes directly from the convergence proof above.

2️⃣ Longest Consecutive Sequence

Problem statement – Given an unsorted array nums, return the length of the longest sequence of consecutive integers.

O(n) solution

• Convert the list to a set for O(1) membership tests.
• For each number, check whether it is the start of a sequence (num‑1 not in the set).
• If it is a start, walk forward (num+1, num+2, …) counting the streak length.

def longestConsecutive(self, nums: List[int]) -> int:
    num_set = set(nums)          # O(n) building the hash table
    longest = 0

    for num in num_set:
        # Skip if not the beginning of a sequence
        if (num - 1) not in num_set:
            cur = num
            streak = 1
            while (cur + 1) in num_set:
                cur += 1
                streak += 1
            longest = max(longest, streak)

    return longest

Why a set instead of a list?
A Python set is backed by a hash table, giving average‑case O(1) look‑ups, whereas a list would require O(n) scans.

3️⃣ Merge Intervals

Problem statement – Given an array intervals where each element is [start, end], merge all overlapping intervals and return the resulting non‑overlapping intervals.

Greedy approach (O(n log n))

1. Sort intervals by their start time.
2. Iterate through the sorted list, merging when the current interval overlaps the last one in the result list.

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []

    # 1️⃣ Sort by start time (in‑place, O(n log n))
    intervals.sort(key=lambda x: x[0])

    merged = []
    for cur_start, cur_end in intervals:
        # If no overlap, start a new interval
        if not merged or merged[-1][1] < cur_start:
            merged.append([cur_start, cur_end])
        else:
            merged[-1][1] = max(merged[-1][1], cur_end)

    return merged

4️⃣ Insert Interval

Problem statement – Given a sorted, non‑overlapping list of intervals intervals and a new interval newInterval, insert newInterval into intervals and merge if necessary, preserving the sorted order and non‑overlapping property.
The problem is essentially merge intervals after inserting the new one.

Implementation

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    if not intervals:
        return [newInterval]

    # Insert newInterval into the correct position to keep the list sorted
    inserted = False
    result = []
    for start, end in intervals:
        if not inserted and start > newInterval[0]:
            result.append(newInterval)
            inserted = True
        result.append([start, end])

    if not inserted:                     # newInterval belongs 

마지막에

result.append(newInterval)

# Now merge the (still sorted) list – reuse the merge logic
merged = []
for cur_start, cur_end in result:
    if not merged or merged[-1][1] < cur_start:
        merged.append([cur_start, cur_end])
    else:
        merged[-1][1] = max(merged[-1][1], cur_end)

return merged

알고리즘

1. Insert newInterval를 적절한 위치에 삽입합니다 (정렬된 순서를 유지).
2. Merge 결과 리스트를 Merge Intervals 문제와 동일한 탐욕적 기법을 사용해 병합합니다.

솔루션에서 자주 보이는 추가 스니펫

inserted = True
break

if inserted == False:
    intervals.append(newInterval)

for start, end in intervals:
    if not res or res[-1][1] < start:
        res.append([start, end])
    else:
        res[-1][1] = max(res[-1][1], end)
return res

• inserted라는 플래그는 새 구간이 이미 삽입되었는지 여부를 추적합니다.
• 반복이 끝난 후 플래그가 여전히 False이면, 새 구간을 리스트 끝에 추가합니다.
• 마지막 루프는 위와 동일한 로직으로 겹치는 구간들을 병합합니다.

TL;DR

스니펫을 자유롭게 복사하고, 실험해 보며, 자신의 코딩 스타일에 맞게 적용하세요. 즐거운 코딩 되세요! 🚀