Frequency Sort

Problem Statement

Sort the elements of an array by frequency in descending order. Elements with higher frequency come first. For equal frequencies, any stable tie-break is acceptable unless otherwise specified.

Input

An integer array nums.

nums = [1, 1, 2, 2, 2, 3]

Output

The elements reordered so higher-frequency values come first.

[2, 2, 2, 1, 1, 3]
 
// freq: 2→3, 1→2, 3→1
// emit 2's first, then 1's, then 3

Constraints

• 1 ≤ nums.length ≤ 10⁵
• Values may be any integer (works identically for strings — LeetCode 451 variant).

Intuition

Count frequencies, then repeatedly pull the most frequent element and emit that many copies. “Most frequent at top” = max-heap keyed on frequency. Unlike Top-K, we don’t cap the heap — we need all elements in output order.

freq:  {1:2, 2:3, 3:1}
heap (max by count):  [(3,2), (2,1), (1,3)]
 
pop (3,2) → emit [2,2,2]   result = [2,2,2]
pop (2,1) → emit [1,1]     result = [2,2,2,1,1]
pop (1,3) → emit [3]       result = [2,2,2,1,1,3] ✓

Solution

import heapq
from collections import Counter
 
def frequencySort(nums: list[int]) -> list[int]:
    freq = Counter(nums)
    max_heap = [(-cnt, val) for val, cnt in freq.items()]   # negate → max-heap
    heapq.heapify(max_heap)                                  # O(u)
 
    result: list[int] = []
    while max_heap:
        neg_cnt, val = heapq.heappop(max_heap)
        result.extend([val] * (-neg_cnt))
    return result

function frequencySort(nums: number[]): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
 
  const h = new Heap<[number, number]>((a, b) => b[0] - a[0]);   // max-heap by count
  for (const [val, cnt] of freq) h.push([cnt, val]);
 
  const out: number[] = [];
  while (h.size > 0) {
    const [cnt, val] = h.pop()!;
    for (let i = 0; i < cnt; i++) out.push(val);
  }
  return out;
}

Complexity

Edge Case Thinking