What is there is another requirement of this problem: "if two numbers have the same frequency, the smaller one should have the priority". Is this solution still working?

Solution 1 runs in linear time. Both 2 & 3 runs in O(NlogN) time, and that's not what the interviewer expects you to do. Though what I came up with at first are exactly solution 2 & 3 lol. Anyways nice post! Thanks!