Minimum Swaps To Group All 1's Together: Sliding Window Trên Mảng Nhị Phân

Đề bài: Cho mảng nhị phân data. Tìm số lần swap tối thiểu để gom tất cả các 1 thành một khối liên tục.

Ví dụ: [1,0,1,0,1,0,0,1,1,0,1] → 3 swaps (kết quả: [0,0,0,0,0,1,1,1,1,1,1]).

Quan sát

• Tổng số 1 trong mảng = k (kích thước cửa sổ mục tiêu).
• Cần tìm cửa sổ độ dài k chứa nhiều 1 nhất → số 0 trong cửa sổ đó = số swap cần thiết.
• Số swap = k - max_ones_in_window.

Thuật toán: Sliding Window + Prefix Sum

1. Đếm tổng số 1 → k.
2. Tính prefix sum mảng data.
3. Sliding window độ dài k: số 1 trong window [l, r] = prefix[r] - prefix[l-1].
4. Tìm max số 1 → kết quả = k - max_ones.

Code Python

class Solution:
    def minSwaps(self, data: list[int]) -> int:
        n = len(data)
        k = sum(data)  # tổng số 1 = kích thước window
        
        if k <= 1:
            return 0  # Đã gom hoặc không có 1
        
        # Prefix sum
        prefix = [0] * n
        prefix[0] = data[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + data[i]
        
        # Window đầu tiên [0, k-1]
        max_ones = prefix[k-1]
        
        # Slide window
        for r in range(k, n):
            l = r - k + 1
            ones_in_window = prefix[r] - prefix[l-1]
            max_ones = max(max_ones, ones_in_window)
        
        return k - max_ones

# Test
ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))  # 3
print(ob.minSwaps([1,0,1,0,1]))              # 1
print(ob.minSwaps([0,0,0]))                  # 0
print(ob.minSwaps([1,1,1]))                  # 0

Tối ưu: Không cần prefix sum mảng riêng

def minSwaps(self, data):
    k = sum(data)
    if k <= 1: return 0
    
    # Window đầu
    curr_ones = sum(data[:k])
    max_ones = curr_ones
    
    # Slide
    for i in range(k, len(data)):
        curr_ones += data[i] - data[i-k]
        max_ones = max(max_ones, curr_ones)
    
    return k - max_ones

Phân tích

• Time: O(n)
• Space: O(1) (phiên bản tối ưu)

Kết luận

Sliding window trên mảng nhị phân là pattern phổ biến. Bài này biến đổi "min swaps" thành "max 1s in fixed window".