0

I was trying to solve this problem in leetcode. problem: heap problem

this is my code:

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        priority_queue<pair<int,int>,vector<pair<int,int>>>mxheap;
        
        for(int i=0; i<score.size(); i++){
            mxheap.push({score[i],i});
        }
        
        vector<string>ans(score.size());
        int place = 1;
        while(!mxheap.empty()){
            
            switch(place){
                case 1:  
                    ans[mxheap.top().second] = "Gold Medal";
                    mxheap.pop(); 
                    break;
                case 2:
                    ans[mxheap.top().second] = "Silver Medal";
                    mxheap.pop();
                    break;
                case 3:
                    ans[mxheap.top().second] = "Bronze Medal";
                    mxheap.pop();
                    break;
                default:
                    ans[mxheap.top().second] = to_string(place);
            }
            place++;
        }
        return ans;
    }
};

I don't know why I am getting the time limit exceeds I also tried removing the pair and using a map but that also didn't work. I also saw some answers in discuss section those answers were also of (nlogn) time complexity but they worked fine mine is also (nlogn) still its not working can someone please tell me what am I doing wrong here.

Ayushaps1
  • 31
  • 3
  • you will need to debug this. What have you done in debuggiung? – Marcus Müller Jul 23 '21 at 22:05
  • These problems usually require you to know or discover a "Trick" that eliminates most of the work. You likely have not discovered the "Trick" yet. – user4581301 Jul 23 '21 at 22:11
  • Looks like you're missing a pop under the default. Endless loop? Since you want to pop in all cases you could move that outside each case into one place after. – Retired Ninja Jul 23 '21 at 22:17
  • 1
    Find which inputs cause you to time out, set it up as a custom input, add some timings and go from there. https://stackoverflow.com/questions/22387586/measuring-execution-time-of-a-function-in-c might be useful if you haven't timed functions before. – scrappedcola Jul 23 '21 at 22:17
  • You don't need priority queues for this. A simple array of indices, sort the indices based on the scores, and then use the sorted indices when accessing the score array to figure out who comes first, second, third, etc. Look at [this answer](https://stackoverflow.com/questions/40405266/having-trouble-creating-an-array-that-shows-how-the-indices-were-moved-in-anothe/40405691#40405691) explaining how to sort using indices (for your case, use `>` in the sort lambda). – PaulMcKenzie Jul 23 '21 at 22:42
  • Just for laughs, I went to the site, implemented my suggestion to you, and got a success on the first try. I suggest you first sort the indices, look at the sorted index array in the debugger, and from there, you could easily figure out where to place the names in the output vector. – PaulMcKenzie Jul 23 '21 at 22:43
  • 2
    You are getting a TLE because Leetcode is a web site with a list of random coding puzzles based on programming and mathematical tricks that are needed to solve them. Those who don't, and try the direct approach always end up with a result that runs too slow. Unfortunately, these coding puzzle sites do not offer any C++ tutorials or learning material, that explain the fundamentals of C++, and the necessary algorithms behind their coding puzzles. They are not meant to be used by those who want to learn C++, only by those who want to solve meaningless coding puzzles. – Sam Varshavchik Jul 23 '21 at 22:53
  • i am really sorry it wasn't working because i forgot to pop on default case now its working and thanks you all for your suggestions – Ayushaps1 Jul 24 '21 at 10:38

1 Answers1

1

Because you are not popping off the element in the default case.

ans[mxheap.top().second] = to_string(place);
mxheap.pop(); // Add this

which leads to an infinite while loop since your queue never becomes empty and hence the TLE.

You should be using a debugger to root-cause these problems and add breakpoints in your program to verify the expected program state at those points.

Zoso
  • 3,273
  • 1
  • 16
  • 27