Day 22: 100 Days of DSA

Welcome to Day 22 of my 100 Days of DSA challenge! Today, I solved five problems focused on priority queues. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

1. Solve the "reorganize string" problem using a priority queue.

Code:

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

// Function to reorganize the string
string reorganizeString(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;

    priority_queue<pair<int, char>> pq;
    for (auto& p : freq) pq.push(make_pair(p.second, p.first));

    string result = "";
    pair<int, char> prev = make_pair(0, ' ');

    while (!pq.empty()) {
        pair<int, char> current = pq.top();
        pq.pop();
        int count = current.first;
        char ch = current.second;

        result += ch;
        if (prev.first > 0) pq.push(prev);
        prev = make_pair(count - 1, ch);
    }

    return result.size() == s.size() ? result : "";
}

int main() {
    string s = "aab";
    cout<<"The string is:"<<s<<endl;
    cout << "Reorganized String: " << reorganizeString(s) << endl;
    return 0;
}

Output:

2. Solve the "top k frequent elements" problem using a priority queue.

Code:

#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;

// Function to find top K frequent elements
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (auto& p : freq) {
        pq.push({p.second, p.first});
        if (pq.size() > k) pq.pop();
    }

    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    return result;
}

int main() {
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> res = topKFrequent(nums, k);
    cout << "Top K Frequent Elements: ";
    for (int n : res) cout << n << " ";
    return 0;
}

Output:

3. Solve the "sort characters by frequency" problem using a priority queue.

Code:

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;

// Function to sort characters by frequency
string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;

    priority_queue<pair<int, char>> pq;
    for (auto& p : freq) {
        pq.push(make_pair(p.second, p.first));
    }

    string result;
    while (!pq.empty()) {
        pair<int, char> current = pq.top();
        pq.pop();
        int count = current.first;
        char ch = current.second;

        result.append(count, ch);
    }
    return result;
}

int main() {
    string s = "tree";
    cout << "Sorted by Frequency: " << frequencySort(s) << endl;
    return 0;
}

Output:

4. Solve the "k closest points to the origin" problem using a priority queue.

Code:

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

// Function to find K closest points to the origin
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<pair<double, vector<int>>> pq;
    for (auto& p : points) {
        double dist = sqrt(p[0] * p[0] + p[1] * p[1]);
        pq.push({dist, p});
        if (pq.size() > k) pq.pop();
    }

    vector<vector<int>> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    return result;
}

int main() {
    vector<vector<int>> points = {{1, 3}, {-2, 2}, {5, 8}};
    int k = 2;
    vector<vector<int>> res = kClosest(points, k);
    cout << "K Closest Points: ";
    for (auto& p : res) cout << "[" << p[0] << ", " << p[1] << "] ";
    return 0;
}

Output:

5. Solve the "connect n ropes to minimize cost" problem using a priority queue.

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to calculate minimum cost to connect ropes
int minCost(vector<int>& ropes) {
    priority_queue<int, vector<int>, greater<>> pq(ropes.begin(), ropes.end());
    int cost = 0;

    while (pq.size() > 1) {
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        cost += first + second;
        pq.push(first + second);
    }
    return cost;
}

int main() {
    vector<int> ropes = {1, 2, 3, 4, 5};
    cout << "Minimum Cost to Connect Ropes: " << minCost(ropes) << endl;
    return 0;
}

Output:

This is all for today!