C++ O(n) solution using PriorityQueue and HashMap

  • 0
        string frequencySort(string s) {
            unordered_map<char,int> mp;
            for (auto& c : s) mp[c]++;
            priority_queue<pair<int, char>> q;
            for (auto& p : mp) q.push(make_pair(p.second, p.first));
            string res;
            while (!q.empty()) {
                pair<int, char> p = q.top();
                res += string(p.first, p.second);
            return res;

  • 0

    Technically this algorithm is O(n logn) rather than O(n), and only string limitations make it O(n). Just a warning for anybody who tries to adopt this algorithm for similar problems :) I.e. in the past I had to deal with a problem where input was a vector of strings and the goal was to print top N most popular strings in the array. Same algorithm applies there as well, but it becomes O(n logn)

    The point of interest is this line:

    for (auto& p : mp) q.push(make_pair(p.second, p.first));

    If your input consists only of unique values, then size of mp is n. Push into priority_queue is O(longn). Since you're calling O(logn) n times, overall complexity is O(n logn).

    But with strings it IS pretty fast! Thanks for sharing :)

  • 0

    No, this line and the while loop are both O(1)

    for (auto& p : mp) q.push(make_pair(p.second, p.first));

    since mp.size() < 128

  • 0

    This doesn't seem to work for my test case:



Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.