LeetCode #128 Longest Consecutive Sequence: เริ่มนับเฉพาะหัวแถว

Longest Consecutive Sequence ถามความยาวลำดับจำนวนเต็มติดกันที่ยาวที่สุดโดย input ไม่เรียง และตั้งเป้าเวลา O(n) เคล็ดลับคือไม่เริ่มเดินจากทุกเลข แต่เริ่มเฉพาะเลขที่ไม่มี value - 1 อยู่ในชุดครับ

วิธี 1: Sort สำเนา

เรียงแล้วเดินครั้งเดียว ข้าม duplicate และ reset เมื่อเกิดช่องว่าง เวลา O(n log n) พื้นที่ขึ้นกับการ sort; ในโค้ดนี้สร้างสำเนาจึงเป็น O(n) อ่านง่ายและเหมาะเมื่อข้อมูลต้องเรียงต่ออยู่แล้ว

วิธี 2: Hash Set (default)

สร้าง set เพื่อตัด duplicate จากนั้นเลขใดไม่มี predecessor ถือเป็นหัวแถว เดินต่อ +1 จนขาด แม้มี while ซ้อน แต่แต่ละเลขถูกเดินในแถวของตัวเองครั้งเดียว จึงเฉลี่ย O(n)

from __future__ import annotations

import unittest


def sorting(nums: list[int]) -> int:
    if not nums:
        return 0
    ordered = sorted(nums)
    best = current = 1
    for before, value in zip(ordered, ordered[1:]):
        if value == before:
            continue
        current = current + 1 if value == before + 1 else 1
        best = max(best, current)
    return best


def hash_set(nums: list[int]) -> int:
    values = set(nums)
    best = 0
    for value in values:
        if value - 1 in values:
            continue
        length = 1
        while value + length in values:
            length += 1
        best = max(best, length)
    return best


class ConsecutiveTests(unittest.TestCase):
    def test_both_methods(self):
        cases = [
            ([], 0),
            ([100, 4, 200, 1, 3, 2], 4),
            ([0, 3, 7, 2, 5, 8, 4, 6, 0, 1], 9),
            ([-2, -1, -1, 0, 2], 3),
        ]
        for solve in (sorting, hash_set):
            for nums, expected in cases:
                self.assertEqual(solve(nums), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Sort	Hash set
เวลา	O(n log n)	เฉลี่ย O(n)
พื้นที่ในตัวอย่าง	O(n)	O(n)
duplicate	ต้องข้าม	ถูกตัดอัตโนมัติ
รักษา input	ใช่ เพราะ sort สำเนา	ใช่
worst-case hash	ไม่เกี่ยว	ขึ้นกับ hash implementation
input ต้องเรียงต่อ	เหมาะ	ไม่จำเป็น

Recap

• คืน 0 สำหรับ input ว่าง
• ตัดหรือข้าม duplicate
• เริ่มเดิน hash set เฉพาะเมื่อไม่มี predecessor
• ใช้ sort เมื่อผลลัพธ์เรียงมีประโยชน์ต่อขั้นถัดไป