Sort by frequency

Rearrange a list so elements appear in decreasing order of frequency, breaking ties by original order.

sorting frequency dictionaries lists

Write a function `sort_by_frequency(lst)` that takes a list of integers and returns a new list where all elements are sorted by decreasing frequency (how many times they appear in the original list). If two elements have the same frequency, keep their relative order from the original list (i.e., stable sorting by frequency only). The returned list must contain exactly the same elements as the input, just reordered.

Constraints

- The input list may contain any integers (including negatives).
- Length of the list: 0 to 10,000.
- The algorithm should run in O(n log n) time or better.

Example

>>> sort_by_frequency([4, 1, 4, 2, 1, 1])
[1, 1, 1, 4, 4, 2]
>>> sort_by_frequency([])
[]
>>> sort_by_frequency([5, 5, 3, 3, 2])
[5, 5, 3, 3, 2]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count frequencies with a dictionary.

Use the frequency as a key in a stable sort (e.g., sorted with key=lambda x: -freq[x]).

Python's sort is stable, so if you only sort by negative frequency, original order is preserved for ties.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.