There's an O(N) time & space solution for this question using a slightly modified version of Bucket Sort, specifically useful for this type of question (top K frequent numbers/ letters- see Bucket Sort filtered questions on Leetcode).

Its usage for optimal solutions isn't common, but it still might be useful to link to/ mention this idea.