Sort an array of integers by the frequency of each value, least frequent first. When two values have the same frequency, put the larger value first.
Before you code
This is a sort by two keys: frequency ascending, then value descending. Count first, then express both keys in one sort.
Hints
- Count each value with a hash map.
- Sort with the key
(count[x], -x): the first component orders by frequency, and the negated value breaks ties in decreasing order. - Alternatively, sort twice with a stable sort: first by value descending, then by frequency. Why must the first sort be the tie-breaker?
Production & complexity notes
When solving Sort array by increasing frequency on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stability and what libraries use to reinforce the underlying pattern.
What it practices
Multi-key sorting, with a composite key or with stable passes, from Stability and what libraries use.