// Runtime: 12 ms, faster than 58.41% of Java online submissions for Top K Frequent Words.
// Memory Usage: 38.9 MB, less than 67.86% of Java online submissions for Top K Frequent Words.
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freqMap = new HashMap<>();

        ArrayList<SortedSet<String>> wordsByFreq = new ArrayList<>();
        for (int i = 0; i <= words.length; i++) wordsByFreq.add(new TreeSet<String>());

        for (String word: words) {
            Integer freq = freqMap.get(word);

            if (freq == null) {
                freqMap.put(word, 1);
                wordsByFreq.get(1).add(word);
            } else {
                wordsByFreq.get(freq).remove(word);
                freq++;
                wordsByFreq.get(freq).add(word);
                freqMap.put(word, freq);
            }
        }

        List<String> result = new ArrayList<>();
        for (int freq = words.length; freq >0 && result.size() < k; freq--) {
            for (String word: wordsByFreq.get(freq)) {
                result.add(word);
                if (result.size() >= k) break;
            }
        }
        return result;
    }
}