Longest Consecutive Sequence: thủ thuật O(n) bỏ qua việc đếm thừa

Sắp xếp mảng sẽ làm bài này trở nên tầm thường: quét từ trái sang phải, theo dõi lượt chạy hiện tại. Đó là O(n log n). Đề bài yêu cầu tường minh O(n). Vậy sorting bị loại — không phải vì khó viết, mà vì constraint nói như vậy. Đúng một hạn chế duy nhất đó là toàn bộ câu đố.

Constraint ép buộc điều gì

0 <= nums.length <= 10^5. Mảng có thể rỗng. Tối đa 100,000 phần tử nghĩa là O(n log n) sort có thể chấp nhận trên thực tế, nhưng đề bài cấm tường minh.

-10^9 <= nums[i] <= 10^9. Khoảng giá trị này rộng 2 tỷ. Bucket sort và index trick cần một mảng kích thước đó — không khả thi. Khoảng này cũng loại bỏ mọi thủ thuật kiểu "dịch chuyển tất cả về bắt đầu từ 0". Bạn cần một cấu trúc cho phép query membership O(1) mà không cần quan tâm đến giá trị thực, tức là hash table.

Duplicate là hợp lệ. Ví dụ thứ ba [1, 0, 1, 2] có hai số 1 và đáp án vẫn là 3 (dãy [0, 1, 2]). Hash set tự động gộp duplicate.

Constraint O(n) không phải gợi ý nhẹ — đó là cổng cứng loại bỏ mọi thứ trừ hash-based lookup. Khi thấy điều đó, ba approach hiện ra tự nhiên: O(n²) naive (dùng list lookup), bước tạm dừng ở O(n log n) qua sorting, và hash set solution thực sự thỏa constraint.

Brute force: O(n²)

Trước khi đến solution tối ưu, hãy xét approach naive. Với mỗi số, kiểm tra xem nó có phải điểm bắt đầu dãy liên tiếp không bằng cách xác nhận predecessor vắng mặt, rồi đếm lên bằng linear search qua các giá trị đã dedup.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        best = 0
        num_list = list(set(nums))  # dedup trước
        for n in num_list:
            if n - 1 not in num_list:  # O(n) list membership
                length = 1
                while n + length in num_list:  # O(n) mỗi lần gọi
                    length += 1
                best = max(best, length)
        return best

public class Solution {
    public int LongestConsecutive(int[] nums) {
        var numList = nums.Distinct().ToList();
        int best = 0;
        foreach (int n in numList) {
            if (!numList.Contains(n - 1)) {  // O(n) list search
                int length = 1;
                while (numList.Contains(n + length))  // O(n) mỗi lần gọi
                    length++;
                best = Math.Max(best, length);
            }
        }
        return best;
    }
}

Toán tử in trên list (và List<T>.Contains trong C#) là O(n) — nó scan từ đầu mỗi lần. Vòng ngoài là O(n). While bên trong có thể chạy O(n) bước. Tổng: O(n²). Với n = 10^5, đó là 10^10 phép tính — mười giây hoặc hơn trên phần cứng thông thường. Quá chậm.

Cách sửa rất đơn giản: đổi list thành hash set. Không có gì khác thay đổi.

Sorting: O(n log n)

Sort, loại bỏ duplicate, rồi scan tìm run liên tiếp. Sau khi sort, mọi dãy liên tiếp đều nằm trong một khối liền kề trong mảng, nên một lần quét trái-phải tìm được tất cả.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0
        nums = sorted(set(nums))
        best = 1
        current = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                current += 1
                best = max(best, current)
            else:
                current = 1
        return best

public class Solution {
    public int LongestConsecutive(int[] nums) {
        if (nums.Length == 0) return 0;
        int[] sorted = nums.Distinct().OrderBy(x => x).ToArray();
        int best = 1, current = 1;
        for (int i = 1; i < sorted.Length; i++) {
            if (sorted[i] == sorted[i - 1] + 1) {
                current++;
                best = Math.Max(best, current);
            } else {
                current = 1;
            }
        }
        return best;
    }
}

O(n log n) do bước sort. Distinct / set() xử lý duplicate — hai giá trị giống nhau trong input sẽ tạo ra hai phần tử bằng nhau liền kề trong mảng đã sort, mà check nums[i] == nums[i-1] + 1 sẽ không đếm là liên tiếp. Gộp lại trước khi scan thì gọn hơn. Logic sau khi sort đơn giản và dễ đọc.

Nhưng O(n log n) vi phạm constraint. Sorting bị loại — không phải vì không thực tế, mà vì đề bài nói vậy.

Bước đi tối ưu: hash set với sequence-start detection

Insight then chốt là chỉ cần đếm từ sequence starts — những số không có hàng xóm bên trái trong input. Mọi số khác sẽ được quét lên như một phần của run bắt đầu ở bên trái. Điều này có nghĩa là vòng ngoài có thể bỏ qua hầu hết phần tử, và vòng while bên trong chỉ chạy cho các start thực sự.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        best = 0
        for n in num_set:
            if n - 1 not in num_set:      # n là sequence start
                length = 1
                while n + length in num_set:
                    length += 1
                best = max(best, length)
        return best

public class Solution {
    public int LongestConsecutive(int[] nums) {
        var numSet = new HashSet<int>(nums);
        int best = 0;
        foreach (int n in numSet) {
            if (!numSet.Contains(n - 1)) {     // n là sequence start
                int length = 1;
                while (numSet.Contains(n + length))
                    length++;
                best = Math.Max(best, length);
            }
        }
        return best;
    }
}

Tại sao vòng lặp lồng nhau vẫn là O(n)

Có cấu trúc lồng nhau ở đây: for bên ngoài và while bên trong. Lo ngại tự nhiên là O(n²). Không phải vậy.

Mỗi phần tử trong set được chạm bởi while bên trong nhiều nhất một lần, trên toàn bộ quá trình thực thi. Xét bất kỳ phần tử k nào. Hoặc k - 1 có trong set — khi đó k không qua được kiểm tra sequence-start và vòng ngoài bỏ qua nó — hoặc k - 1 vắng mặt, nghĩa là k là một start và while đếm tiếp từ k. While chỉ đến k trong lúc quét tiếp nếu một start nhỏ hơn đã kích hoạt nó. Không phần tử nào vừa được đếm trong while vừa đóng vai start trong vòng ngoài. Hai vai trò này loại trừ lẫn nhau.

Trên tất cả các lần lặp kết hợp, tổng số bước của while bên trong nhiều nhất là n — một bước mỗi phần tử trong set. Tổng công việc là O(n) để build set cộng O(n) cho quá trình duyệt hai vai. Lý luận amortized này giống với justification cho union-find path compression.

Trace tay: [100, 4, 200, 1, 3, 2]

num_set = {1, 2, 3, 4, 100, 200} sau khi construction.

Thứ tự duyệt qua set không được đảm bảo — Python set có thứ tự nội bộ riêng — nhưng kết quả giống hệt nhau bất kể thứ tự. Phần tử 2, 3, 4 bị bỏ qua trong vòng ngoài và thay vào đó được đếm khi n = 1 chạy while bên trong. Mỗi phần tử được xử lý đúng một lần.

Ví dụ thứ hai: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]. Sau dedup, num_set = {0, 1, 2, 3, 4, 5, 6, 7, 8}. Sequence start duy nhất là 0 — mọi số khác đều có hàng xóm trái. While bên trong chạy từ 0 đến 8, chín bước, cho length 9.

Edge cases

Mảng rỗng. best khởi tạo là 0. Thân vòng for không bao giờ thực thi. Hàm trả về 0 đúng. Guard if not nums: return 0 cũng đúng nhưng thừa — code xử lý được mà không cần.

Một phần tử. [5] — 4 không trong set, nên 5 là sequence start. Thân while không bao giờ thực thi (6 vắng mặt). Return 1.

Toàn duplicate. [1, 1, 1] — sau khi tạo set, chỉ còn 1. 0 không trong set, nên 1 là sequence start. Length là 1. Return 1. Set constructor làm công việc dedup; không cần xử lý duplicate thủ công.

Không có cặp liên tiếp nào. [1, 3, 5, 7] — mỗi phần tử là sequence start, mỗi while kết thúc ngay. Mỗi length là 1. Return 1. Bốn start, bốn dãy đơn phần tử.

Số âm. [-1, 0, 1] — -1 không có predecessor -2 trong set, nên nó là start. While đếm -1 -> 0 -> 1. Length 3. Return 3. Số âm không có gì đặc biệt; số học n - 1 và n + length hoạt động y hệt.

So sánh các approach

Cả ba đều dùng O(n) space — hoặc cho mảng đã sort và dedup, hoặc cho hash set. Sự khác biệt có ý nghĩa duy nhất là time.

Mental model mà bài toán này dạy

Approach sorting hỏi: sắp xếp phần tử, rồi scan tìm run. Approach hash set đặt câu hỏi khác: phần tử nào là sequence starts? Đây là hai cách đặt vấn đề khác nhau cho cùng một dữ liệu.

"Sequence start = phần tử không có hàng xóm trái trong set" là anchor. Khi đã có điều đó, phát hiện start tốn O(1) mỗi phần tử (một hash lookup), và đếm từ một start tốn O(length của dãy đó). Cộng lại trên tất cả start, tổng công việc đếm bằng số phần tử trong set — O(n).

Pattern này tổng quát hóa được. Khi cần phát hiện adjacency hay neighbourhood trong dữ liệu chưa sort mà không muốn sort, hash set cho phép hỏi "hàng xóm của tôi có tồn tại không?" trong O(1). Thủ thuật sequence-start là một trường hợp của move tổng quát đó. Two Sum dùng cơ chế tương tự theo hướng khác — kiểm tra xem target - n có trong set không thay vì n - 1.

Tôi sẽ ship hash set solution trong production. Approach sorting dễ đọc hơn với người chưa quen pattern này, nhưng sự khác biệt O(n log n) vs O(n) có ý nghĩa với input lớn, và version hash set không khó hiểu hơn đáng kể khi đã quen với sequence-start detection.

Related problems

• LeetCode 217 - Contains Duplicate: hash set membership cơ bản; dạng đơn giản nhất của pattern "lưu giá trị vào set, query tồn tại"
• LeetCode 268 - Missing Number: tìm khoảng trống trong dãy liên tiếp; cùng ý tưởng set-membership nhưng hỏi cái gì vắng mặt thay vì cái gì hiện diện
• LeetCode 41 - First Missing Positive: số dương đầu tiên vắng mặt trong mảng chưa sort; thêm twist là muốn giá trị thiếu nhỏ nhất, không phải run dài nhất
• LeetCode 594 - Longest Harmonious Subsequence: subsequence dài nhất với max - min == 1; dùng hash map frequency count thay vì set, thêm chiều đếm vào adjacency query