Vector with Custom Comparator fails for inputs with large values.


  • 0
    B

    Link to problem : https://leetcode.com/problems/sort-characters-by-frequency/description/

    So recently I thought why use a priority queue and use a plain vector with custom comparator to sort in descending order of frequency. My code works for cases where input size is small.

    Can someone tell me what am I doing incorrectly ? Or is it just the memory limitation of the machine.

    Encountered Error : malloc(): memory corruption: 0x00000000024cde80 ***
    
    //////////
    // Code //
    //////////
    class Solution {
    public:
        string frequencySort(string s) {
           std::vector<std::pair<int, int>> vec(57, std::make_pair(0, 0));
            auto comp = [](std::pair<char, int> a, std::pair<char, int> b) {
                return a.second > b.second;
            };
            for(char c : s) {
                vec[c - 'A'].first = c - 'A';
                ++vec[c - 'A'].second;
            }
            // Sort using the above declared comparator "comp"
            std::sort(vec.begin(), vec.end(), comp);
            // Show for debugging
            show(vec);
            std:string res;
            for(std::pair<int, int> pr : vec) {
                if(pr.first == 0)
                    break;
                for(size_t i = 0; i < pr.second; i++)
                    res.push_back(pr.first + 'A');
            }
            return res;
        }
    private:
    // For Debugging    
    void show(std::vector<std::pair<int, int>>& vec) {
            for(auto pr : vec) {
                if(pr.first != 0)
                    std::cout << (char)(pr.first + 'A') << " : " << pr.second << std::endl;
            }
        }
    };
    

Log in to reply
 

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