Hi folks! This is a short article shows where we can apply priority queue (pq) to solve problems. Some problems are taken from recent leetcode contests where pq is often used.
Please post problems related to pq in a comment that you recently solved during some contest or interview, so more people can practive this type of problems!
Remove redundant element that is no more fulfill requirement:
// Easy one
KthLargest(int k, vector<int>& nums) {
kel = k;
for (auto n : nums) {
pq.push(n);
if (pq.size() > k) pq.pop(); // Remove element as it is not fulfill problem requirement anymore.
}
}Related problems:
- Top K frequent words: https://leetcode.com/problems/top-k-frequent-words/
- Kth Largest Element in a Stream: https://leetcode.com/problems/kth-largest-element-in-a-stream/
Add new element to the pq if future calculation will depend on the current calculated value:
// Can be solved more efficiently.
int maximumScore(int a, int b, int c) {
priority_queue<int> pq;
pq.push(a);
pq.push(b);
pq.push(c);
int res = 0;
while (pq.size() >= 2) {
int lhs = pq.top(); pq.pop();
int rhs = pq.top(); pq.pop();
res++; lhs--; rhs--;
if (lhs) pq.push(lhs); // Insert element into pq to use in next iteration.
if (rhs) pq.push(rhs); // Insert element into pq to use in next iteration.
}
return res;
}
Related problems:
- Minimum Cost to Connect Sticks: https://leetcode.com/problems/minimum-cost-to-connect-sticks/
- Maximum Score From Removing Stones: https://leetcode.com/problems/maximum-score-from-removing-stones/
- Maximum Average Pass Ratio: https://leetcode.com/problems/maximum-average-pass-ratio/
- Number of Orders in the Backlog: https://leetcode.com/problems/number-of-orders-in-the-backlog/
Remove/Insert element to/from pq while preserving problem invariant:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
sort(intervals.begin(), intervals.end());
auto temp = queries;
sort(temp.begin(), temp.end());
using ip = pair<int, int>;
priority_queue<ip, vector<ip>, greater<ip>> pq;
unordered_map<int, int> hmap;
int i = 0, sz = intervals.size();
for (auto& q : temp) {
while (i < sz && intervals[i][0] <= q) {
int l = intervals[i][0];
int r = intervals[i][1];
pq.push({r - l + 1, r}); // Insert element -> it can be a potential answer.
i++;
}
while (!pq.empty() && pq.top().second < q) pq.pop(); // Remove elements that can't meet requirement.
hmap[q] = pq.empty() ? -1 : pq.top().first;
}
vector<int> res;
for (auto& q : queries) {
res.push_back(hmap[q]);
}
return res;
}Related problems:
- Meeting Rooms II: https://leetcode.com/problems/meeting-rooms-ii/
- Maximum Ice Cream Bars: https://leetcode.com/problems/maximum-ice-cream-bars/
- Minimum Interval to Include Each Query: https://leetcode.com/problems/minimum-interval-to-include-each-query/
Having two pq to track smallest and largest value at the same time:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() * 6 < nums2.size() || nums2.size() * 6 < nums1.size())
return -1;
int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
if (sum1 > sum2) swap(nums1, nums2);
priority_queue<int, vector<int>, greater<int>> minpq(nums1.begin(), nums1.end());;
priority_queue<int> maxpq(nums2.begin(), nums2.end());
int diff = abs(sum1 - sum2);
int op = 0;
while (diff > 0) { // while we have some sum difference between two arrays.
op++;
if (minpq.empty() || (!maxpq.empty() && maxpq.top() - 1 > 6 - minpq.top())) {
diff -= (maxpq.top() - 1); // We will try to remove element from one of the pq,
maxpq.pop();
} else {
diff -= (6 - minpq.top()); // which will faster reduce the sum difference between original arrays.
minpq.pop();
}
}
return op;
}Related problems:
- Equal Sum Arrays With Minimum Number of Operations: https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/
Comments (2)