C++-এ সাবঅ্যারে আকার K-তে সর্বোচ্চ অনন্য উপাদান (Maximum Unique Element in Subarray of Size K)

এই সমস্যাতে, একটি পূর্ণসংখ্যা অ্যারে এবং একটি পূর্ণসংখ্যা K দেওয়া থাকে। আমাদের কাজ হল আকার K-এর প্রতিটি সাবঅ্যারেতে ডুপ্লিকেট ছাড়া সর্বোচ্চ অনন্য (unique) উপাদান বের করা।

উদাহরণ

ইনপুট: array = {4, 1, 1, 3, 3}, k = 3

আউটপুট: 4 3 1

ব্যাখ্যা:

Subarray {4, 1, 1}: অনন্য = {4}, সর্বোচ্চ = 4
Subarray {1, 1, 3}: অনন্য = {3}, সর্বোচ্চ = 3
Subarray {1, 3, 3}: অনন্য = {1}, সর্বোচ্চ = 1

স্লাইডিং উইন্ডো + হ্যাশ টেবিল + BST পদ্ধতি

স্লাইডিং উইন্ডো ব্যবহার করে O(n log k) সময়ে সমাধান করা যায়:

হ্যাশ টেবিল (map) দিয়ে প্রতিটি উপাদানের ফ্রিকোয়েন্সি ট্র্যাক করুন
সেট (set) দিয়ে শুধু অনন্য উপাদানগুলো রাখুন (BST হওয়ায় সর্বোচ্চ পাওয়া সহজ)
উইন্ডো স্লাইড করার সময় পুরনো উপাদান বাদ দিন, নতুন উপাদান যোগ করুন

C++ প্রোগ্রাম উদাহরণ

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

void maxUniqueSubArrayElement(int A[], int N, int K) {
    map<int, int> eleCount;
    for (int i = 0; i < K - 1; i++)
        eleCount[A[i]]++;
    
    set<int> uniqueMax;
    for (auto x : eleCount)
        if (x.second == 1)
            uniqueMax.insert(x.first);
    
    for (int i = K - 1; i < N; i++) {
        eleCount[A[i]]++;
        if (eleCount[A[i]] == 1)
            uniqueMax.insert(A[i]);
        else
            uniqueMax.erase(A[i]);
        
        if (uniqueMax.size() == 0)
            cout << "-1\t";
        else
            cout << *uniqueMax.rbegin() << "\t";
        
        int x = A[i - K + 1];
        eleCount[x]--;
        if (eleCount[x] == 1)
            uniqueMax.insert(x);
        if (eleCount[x] == 0)
            uniqueMax.erase(x);
    }
}

int main() {
    int a[] = {4, 3, 2, 2, 3, 5};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
    cout << "The maximum unique element for a subarray of size " << k << " is\n";
    maxUniqueSubArrayElement(a, n, k);
    return 0;
}

আউটপুট

The maximum unique element for a subarray of size 4 is
4	-1	5