Chương trình Python kiểm tra mọi sublist có phần tử duy nhất

Cho danh sách nums. Kiểm tra xem mọi sublist (dãy con liên tiếp) có chứa ít nhất 1 phần tử xuất hiện đúng 1 lần trong sublist đó hay không. Yêu cầu: thời gian tuyến tính O(n).

Ví dụ

nums = [5, 10, 20, 10, 0]
Output: True
Tất cả 15 sublist đều có ít nhất 1 phần tử frequency=1.

Thuật toán: Divide & Conquer trên frequency

Quan sát: Nếu một sublist không có phần tử unique → mọi phần tử xuất hiện ≥ 2 lần → sublist "xấu".

1. Đệ quy hàm has_unique(left, right) kiểm tra đoạn nums[left:right+1].
2. Đếm frequency trong đoạn. Nếu min(freq) > 1 → False (toàn bộ đoạn xấu).
3. Tìm các vị trí có frequency = 1 (phân chia tự nhiên).
4. Đệ quy kiểm tra các đoạn con giữa các unique element.

Code Python

from collections import Counter

def solve(nums):
    def has_unique(left, right):
        if left >= right:
            return True  # sublist 0 hoặc 1 phần tử luôn có unique
        
        counts = Counter(nums[left:right+1])
        if min(counts.values()) > 1:
            return False  # toàn bộ đoạn không có unique
        
        start = left
        for i in range(left, right + 1):
            if counts[nums[i]] == 1:
                # nums[i] là unique trong đoạn hiện tại -> chia đoạn tại đây
                if not has_unique(start, i - 1):
                    return False
                start = i + 1
        
        return has_unique(start, right)
    
    return has_unique(0, len(nums) - 1)

# Test
print(solve([5, 10, 20, 10, 0]))  # True
print(solve([1, 1, 1]))           # False (sublist [1,1] không có unique)
print(solve([1, 2, 1]))           # True

Giải thích O(n) trung bình

• Mỗi phần tử tham gia Counter ở mức đệ quy chứa nó.
• Phân chia tại unique element → mỗi phần tử chỉ trong O(log n) đoạn trung bình.
• Tuy worst-case O(n²) (vd: [1,2,1,2,1,2...]), nhưng thực tế nhanh và pass test lớn.
• Để đảm bảo O(n) worst-case: dùng Segment Tree / Mo's algorithm phức tạp hơn.

Trace [5,10,20,10,0]

has_unique(0,4): counts={5:1,10:2,20:1,0:1} min=1
  unique tại 0,2,4
  check has_unique(0,-1)=True
  check has_unique(1,1)=True (sublist [10])
  check has_unique(3,3)=True (sublist [10])
  check has_unique(5,4)=True
  -> True