Minimum Swaps to Group All 1's Together: สลับให้ 1 ติดกันน้อยที่สุด

โจทย์

กำหนด binary array data หาจำนวนการสลับ (swap) น้อยที่สุด เพื่อให้ 1 ทั้งหมดติดกัน (อยู่ใน contiguous block)

ตัวอย่าง: [1,0,1,0,1,0,0,1,1,0,1] → 3 swaps (ผลลัพธ์: [0,0,0,0,0,1,1,1,1,1,1])

ข้อสังเกตสำคัญ (Key Insight)

• จำนวน 1 ทั้งหมด = k (คงที่)
• เป้าหมาย: หา window ขนาด k ที่มี 1 มากที่สุด (ต้องสลับน้อยที่สุด)
• จำนวน swap = k - (max ones in any window of size k)

อัลกอริทึม: Sliding Window + Prefix Sum

1. นับจำนวน 1 ทั้งหมด = total_ones
2. สร้าง Prefix Sum array prefix[i] = จำนวน 1 ใน data[0:i]
3. Sliding window ขนาด total_ones หา max ones ใน window ใดๆ
4. คำตอบ = total_ones - max_ones_in_window

การติดตั้ง (Python Implementation)

class Solution:
    def minSwaps(self, data: list[int]) -> int:
        n = len(data)
        total_ones = sum(data)
        
        # Edge case: ไม่มี 1 หรือ 1 อยู่ครบแล้ว
        if total_ones <= 1:
            return 0
        
        # Prefix sum
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + data[i]
        
        # Sliding window ขนาด total_ones
        max_ones = 0
        for left in range(n - total_ones + 1):
            right = left + total_ones
            ones_in_window = prefix[right] - prefix[left]
            max_ones = max(max_ones, ones_in_window)
        
        return total_ones - max_ones

# ทดสอบ
ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))  # 3
print(ob.minSwaps([1,1,0,0,1]))               # 0 (already grouped)
print(ob.minSwaps([0,0,0]))                   # 0
print(ob.minSwaps([1,0,1,0,1]))               # 1

Output

3
0
0
1

การวิเคราะห์ตัวอย่าง

data = [1,0,1,0,1,0,0,1,1,0,1]
total_ones = 6
Window size = 6

Windows:
[1,0,1,0,1,0] → 3 ones
[0,1,0,1,0,0] → 2 ones
[1,0,1,0,0,1] → 3 ones
[0,1,0,0,1,1] → 3 ones
[1,0,0,1,1,0] → 3 ones
[0,0,1,1,0,1] → 3 ones

max_ones = 3
swaps = 6 - 3 = 3 ✓

Complexity

• Time: O(n) - หนึ่งรอบสร้าง prefix, หนึ่งรอบ sliding window
• Space: O(n) สำหรับ prefix array (สามารถลดเป็น O(1) ได้ด้วย running sum)

Space Optimized Version (O(1) space)

def minSwaps_optimized(self, data):
    total_ones = sum(data)
    if total_ones <= 1:
        return 0
    
    # Initial window
    curr_ones = sum(data[:total_ones])
    max_ones = curr_ones
    
    # Slide window
    for i in range(total_ones, len(data)):
        curr_ones += data[i] - data[i - total_ones]
        max_ones = max(max_ones, curr_ones)
    
    return total_ones - max_ones

สรุป

โจทย์ลดรูปเป็น "หา window ขนาด k ที่มี 1 มากที่สุด" ใช้ Sliding Window + Prefix Sum แก้ได้ O(n) time, O(1) space

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ