Longest Consecutive Sequence

Độ Khó: Medium (Khá khó để nhận ra pattern O(n))

Bài toán

Cho một mảng các số nguyên chưa sắp xếp nums. Hãy tìm độ dài của dãy số liên tiếp dài nhất (consecutive elements sequence). Yêu cầu thuật toán phải chạy trong thời gian $O(n)$.

Ví dụ:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Giải thích: Dãy liên tiếp dài nhất là [1, 2, 3, 4]. Độ dài là 4.

Phân Tích & Tiếp Cận

Cách 1: Sorting

Sắp xếp mảng tăng dần, sau đó duyệt và đếm các phần tử liên tiếp (nums[i] == nums[i-1] + 1).

• Time Complexity: $O(N \log N)$ do sắp xếp.
• Yêu cầu bài toán: $O(N)$. => Cách này KHÔNG đạt.

Cách 2: Hash Set thông minh

Để đạt $O(N)$, ta không thể sort. Ta cần tra cứu $O(1)$.

1. Đưa tất cả số vào một Set để loại bỏ trùng lặp và tra cứu nhanh.
2. Duyệt qua từng số num trong Set.
3. Mấu chốt: Ta chỉ bắt đầu đếm chuỗi khi num là điểm khởi đầu của một chuỗi.
   • Làm sao biết num là khởi đầu? -> Kiểm tra xem num - 1 có trong Set không.
   • Nếu num - 1 không tồn tại -> num là khởi đầu (Left Boundary).
   • Nếu num - 1 tồn tại -> num không phải khởi đầu, bỏ qua (để tránh tính trùng lặp O(N^2)).

Khi tìm được điểm khởi đầu, ta dùng vòng lặp while để kiểm tra num + 1, num + 2... xem chuỗi dài bao nhiêu.

function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);
    let longest = 0;

    for (const num of numSet) {
        // Chỉ xử lý nếu num là điểm bắt đầu của chuỗi
        // (tức là num-1 không tồn tại trong set)
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            // Đếm xem chuỗi kéo dài bao xa
            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longest = Math.max(longest, currentStreak);
        }
    }

    return longest;
}

Tại sao đây là O(N)?

Thoạt nhìn có vẻ là $O(N^2)$ vì có vòng lặp lồng nhau (for và while). Tuy nhiên, hãy phân tích kỹ:

• Điều kiện if (!numSet.has(num - 1)) đảm bảo rằng vòng lặp while chỉ chạy cho số đầu tiên của mỗi chuỗi.
• Ví dụ chuỗi [1, 2, 3, 4].
  • 2, 3, 4 sẽ bị if chặn lại (do 1, 2, 3 có tồn tại).
  • Chỉ có 1 mới lọt vào while.
• Mỗi con số trong mảng chỉ được "ghé thăm" tối đa 2 lần:
  1. Một lần trong vòng for chính.
  2. Một lần trong vòng while (nếu nó thuộc về một chuỗi nào đó). => Tổng số phép tính là $O(N + N) = O(N)$.

Pattern Nhận Diện

Khi bài toán yêu cầu tìm kiếm mối quan hệ giữa các phần tử (như "liên tiếp", "cặp đôi") trong mảng chưa sắp xếp mà đòi hỏi $O(N)$:

1. Nghĩ ngay đến Hash Set để biến không gian tìm kiếm về $O(1)$.
2. Tìm cách định nghĩa "Điểm bắt đầu" để tránh duyệt trùng lặp.

Ứng Dụng Thực Tế

Logic này có thể dùng để phát hiện các khoảng thời gian liên tục (Time Ranges) trong lịch trình, hoặc tìm các chuỗi sự kiện log (Sequence of Events) bị gián đoạn.