একটি m×n মেট্রিক্স mat দেওয়া আছে যেখানে প্রতিটি সারি সর্টেড। প্রতিটি সারি থেকে একটা করে উপাদান নিয়ে অ্যারে বানাতে হবে। সব সম্ভাব্য অ্যারেতের যোগফলের মধ্যে k-তম স্মলেস্ট যোগফল বের করুন।
উদাহরণ: mat = [[1,3,11],[2,4,6]], k=5 -> আউটপুট ৭। প্রথম ৫টি স্মলেস্ট সাম: [1,2],[1,4],[3,2],[3,4],[1,6]। ৫ম যোগফল ৭।
সমাধানের ধাপসমূহ
- প্রায়োরিটি কিউ (min-heap) এবং ২D অ্যারে m ব্যবহার করুন।
- update() ফাংশন: করেন্ট ইন্ডেক্স কম্বিনেশন থেকে পরের সম্ভাব্য কম্বিনেশন জেনারেট করে PQ-তে পুশ করুন।
- প্রাথমিক যোগফল (প্রতিটি সারির প্রথম উপাদান) PQ-তে দিন।
- k বার: PQ থেকে মিন বের করুন, সেটে ভিজিটেড مار্ক করুন, update() কল করুন।
- শেষে রিটার্ন করা মানটি হবে k-তম স্মলেস্ট সাম।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Cmp {
bool operator()(vector<int>& a, vector<int>& b) {
return !(a[0] < b[0]);
}
};
class Solution {
public:
priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
vector<vector<int>> m;
int z;
void update(vector<int>& v, int i, bool ok = false) {
if (i == v.size()) {
if (!ok) return;
int sum = 0;
for (int j = 0; j < v.size(); j++) sum += m[j][v[j]];
vector<int> temp(v.begin(), v.end());
temp.insert(temp.begin(), sum);
pq.push(temp);
return;
}
v[i]++;
if (!ok && v[i] < z) update(v, i+1, true);
v[i]--;
update(v, i+1, ok);
}
int kthSmallest(vector<vector<int>>& mat, int k) {
this->m = mat;
int ret = 0, n = m.size();
z = m[0].size();
for (int i = 0; i < n; i++) ret += m[i][0];
vector<int> temp(n);
temp.insert(temp.begin(), ret);
pq.push(temp);
set<vector<int>> s;
while (k--) {
vector<int> temp = pq.top(); pq.pop();
s.insert(temp);
ret = temp[0];
temp.erase(temp.begin());
update(temp, 0);
while (!pq.empty() && s.count(pq.top())) pq.pop();
}
return ret;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{1,3,11},{2,4,6}};
cout << ob.kthSmallest(v, 5);
return 0;
}
ইনপুট
{{1,3,11},{2,4,6}}
আউটপুট
7
