C++-এ kটি সোর্টেড অ্যারেতে m-তম স্মলেস্ট ভ্যালু বের করুন

kটি ভিন্ন সাইজের সোর্টেড অ্যারে দেওয়া আছে। সেগুলো মার্জ করলে (সোর্টেড أور্ডারে) m-তম স্মলেস্ট এলিমেন্ট কত হবে তা বের করতে হবে।

উদাহরণ

ইনপুট: m = 4, arr = {{4,7}, {2,5,6}, {3,9,12,15,19}}

মার্জড সোর্টেড: 2,3,4,5,6,7,9,12,15,19

৪র্থ এলিমেন্ট: 5 → আউটপুট: 5

অ্যালগরিদম

সিম্পল: মার্জ + সোর্ট (O(N log N))

সব এলিমেন্ট একসাথে নিয়ে সোর্ট করুন, m-1 ইনডেক্স এক্সেস করুন।

ইফিশিয়েন্ট: Min Heap / Priority Queue (O(m log k))

1. প্রতিটি অ্যারের প্রথম এলিমেন্ট মিন-হিপে পুশ করুন: {value, {arrayIdx, elementIdx}}।
2. m বার: হিপ থেকে মিন এক্সট্র্যাক্ট করুন, সেটি i-তম স্মলেস্ট।
3. যদি সেই অ্যারেতে পরবর্তী এলিমেন্ট থাকে, সেটি হিপে পুশ করুন।
4. m-তম এক্সট্র্যাক্টকৃত এলিমেন্টই উত্তর।

C++ প্রোগ্রাম

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

typedef pair<int, pair<int,int>> ppi;

int findMSmallestElement(vector<vector<int>> sortedArr, int m) {
    priority_queue<ppi, vector<ppi>, greater<ppi>> pq;
    for (int i = 0; i < sortedArr.size(); i++)
        pq.push({sortedArr[i][0], {i, 0}});
    int count = 0, i = 0, j = 0;
    while (count < m && !pq.empty()) {
        ppi curr = pq.top(); pq.pop();
        i = curr.second.first;
        j = curr.second.second;
        if (j + 1 < sortedArr[i].size())
            pq.push({sortedArr[i][j+1], {i, j+1}});
        count++;
    }
    return sortedArr[i][j];
}

int main() {
    vector<vector<int>> arr = {{4,7}, {2,5,6}, {3,9,12,15,19}};
    int m = 6;
    cout << m << "th smallest value in k sorted arrays is " << findMSmallestElement(arr, m);
    return 0;
}

আউটপুট

6th smallest value in k sorted arrays is 7

ব্যাখ্যা

• ppi = pair> → {value, {arrayIdx, elementIdx}}।
• greater দিয়ে মিন-হিপ বানানো হয়েছে।
• প্রতিটি এক্সট্র্যাকশনের পর সেই অ্যারের নেক্সট এলিমেন্ট পুশ → হিপ সাইজ সর্বোচ্চ k।
• টাইম: O(m log k), স্পেস: O(k)।

নোট

যদি m মোট এলিমেন্টের চেয়ে বড় হয়, তখন বাউন্ড চেক করুন।