Frequency sort descending

Sort elements by how often they appear, breaking ties by original order.

frequency sorting dict

Given a list of elements (integers or strings), return a new list sorted by frequency (how many times each element appears) in descending order. If two elements appear the same number of times, keep them in the order they first appear in the input list. The output must contain exactly the same elements as the input, with duplicates preserved.

Implement the function:

```python
def frequency_sort(items):
    pass
```

**Input:** A list of hashable elements (e.g., integers, strings). The list may be empty.

**Output:** A list with the same elements reordered as described.

Constraints

The input list length is between 0 and 10^5. All elements are hashable. The order of ties must respect the first occurrence in the original list.

Example

```python
>>> frequency_sort([4, 1, 6, 1, 4, 4])
[4, 4, 4, 1, 1, 6]
>>> frequency_sort(['b', 'a', 'b', 'c', 'a', 'a'])
['a', 'a', 'a', 'b', 'b', 'c']
>>> frequency_sort([])
[]
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count each element using a dictionary.

To preserve first-occurrence order for ties, you need to know the first index of each element.

Sort the unique elements by (-frequency, first_index) and then expand each element frequency times.

Test Results

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