Maximum Unique Integers in Subarray: จำนวน Unique สูงสุดใน Subarray ขนาด M ใน C++

ปัญหา

กำหนดอาร์เรย์ขนาด n และ M หา จำนวน Unique Integers สูงสุด ใน Subarray ขนาด M ใดๆ

ตัวอย่าง: arr=[4,1,2,1,4,3], M=4

• [4,1,2,1] → Unique: {4,1,2} = 3
• [1,2,1,4] → Unique: {1,2,4} = 3
• [2,1,4,3] → Unique: {2,1,4,3} = 4 ← Max

แนวคิด: Sliding Window + Hash Map

Algorithm

1. สร้าง Window ขนาด M แรก นับ Frequency ใน Hash Map
2. นับ Unique ใน Window แรก
3. Slide Window: ทีละ 1 ตำแหน่ง
   • ลบ Element ซ้ายสุด: ลด Frequency, ถ้าเหลือ 0 → Unique--, Erase
   • เพิ่ม Element ขวาสุด: เพิ่ม Frequency, ถ้าเป็น 1 → Unique++
   • Update Max Unique

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

int maxUniqueElement(int a[], int N, int M) {
    unordered_map<int, int> freq;
    int uniqueInWindow = 0;
    
    // Initialize first window
    for (int i = 0; i < M; i++) {
        if (freq[a[i]] == 0) uniqueInWindow++;
        freq[a[i]]++;
    }
    
    int maxUnique = uniqueInWindow;
    
    // Slide window
    for (int i = M; i < N; i++) {
        // Remove leftmost
        int left = a[i - M];
        freq[left]--;
        if (freq[left] == 0) {
            uniqueInWindow--;
            freq.erase(left);
        }
        
        // Add new rightmost
        int right = a[i];
        if (freq[right] == 0) uniqueInWindow++;
        freq[right]++;
        
        maxUnique = max(maxUnique, uniqueInWindow);
    }
    
    return maxUnique;
}

int main() {
    int arr[] = {4, 1, 2, 1, 4, 3};
    int M = 4;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum number of unique elements in sub-array of size " 
         << M << " is " << maxUniqueElement(arr, N, M);  // 4
    return 0;
}

Sliding Window Trace

ความซับซ้อน

• Time: O(n)
• Space: O(M) ≤ O(n)

Input / Output

Input:  arr=[4,1,2,1,4,3], M=4
Output: The maximum number of unique elements in sub-array of size 4 is 4