Sort Array by Increasing Frequency: Custom Sorting with Frequency Counts
Sorting by value is something every programmer learns early. But what happens when the sort order depends on how often each value appears? That is the twist behind LeetCode 1636: Sort Array by Increasing Frequency. It combines frequency counting with custom sorting, two patterns that show up constantly in interviews.
The problem
Given an array of integers, sort it in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order of value.
For example, given nums = [1, 1, 2, 2, 2, 3], the answer is [3, 1, 1, 2, 2, 2]. The value 3 appears once (lowest frequency, so it comes first), 1 appears twice (next), and 2 appears three times (highest frequency, so it comes last).
The brute force approach
You could solve this without any clever sorting. Walk through the array and count how many times each value appears using a dictionary. Then build the result array manually: loop through the frequency counts from 1 up to the maximum frequency, and for each frequency level, collect all values that match, sort those values in descending order, and append each one the appropriate number of times.
from collections import Counter
def frequencySort(nums):
freq = Counter(nums)
max_freq = max(freq.values())
result = []
for f in range(1, max_freq + 1):
group = sorted([v for v, c in freq.items() if c == f], reverse=True)
for v in group:
result.extend([v] * f)
return result
This works, but it is verbose and harder to read. You are doing multiple passes, building intermediate lists, and managing the grouping logic yourself. There is a much cleaner way.
The key insight
Python's sort accepts a key function that controls the sort order. If you pass key=lambda x: (freq[x], -x), Python will sort by frequency ascending first, then by value descending within ties. One line of sorting replaces all the manual grouping logic.
The trick is the tuple (freq[x], -x). Python sorts tuples lexicographically: it compares the first element, and only looks at the second element when the first elements are equal. By negating the value (-x), you flip the natural ascending order into descending order for the tiebreaker.
Step-by-step walkthrough
Step 1: Start with the input array
We need to sort [1, 1, 2, 2, 2, 3] by frequency (ascending), breaking ties by value (descending).
Color coding shows the three distinct values. We need to figure out how often each one appears.
Step 2: Count frequencies with a hash map
Walk through the array and count each value. Use Counter(nums) in Python.
1 appears twice, 2 appears three times, 3 appears once. This becomes our sort key.
Step 3: Define the custom sort key
For each element x, the sort key is (freq[x], -x). This sorts by frequency ascending first, then by value descending within ties.
The negative value ensures that within the same frequency, larger values come first.
Step 4: Sort produces the final result
Python sorts tuples lexicographically: (1, -3) comes before (2, -1), which comes before (3, -2). Each element appears freq times.
Result: [3, 1, 1, 2, 2, 2]. Elements with lower frequency come first. Ties broken by higher value first.
The code
from collections import Counter
class Solution:
def frequencySort(self, nums):
freq = Counter(nums)
nums.sort(key=lambda x: (freq[x], -x))
return nums
Three lines of logic. Counter(nums) builds the frequency map in one pass. nums.sort(...) sorts the array in-place using the custom key. The lambda returns a tuple: frequency first (ascending by default), then negative value (so higher values come first when frequencies tie).
The sort is stable in Python, which means elements with equal sort keys preserve their relative order. This does not matter for correctness here since the tuple key fully determines the order, but it is good to know when working with custom sort keys in general.
The Counter class from Python's collections module is a specialized dictionary that counts hashable objects. Counter([1, 1, 2, 2, 2, 3]) produces {1: 2, 2: 3, 3: 1}. Accessing freq[x] is O(1), so the key function adds no extra overhead per comparison.
Complexity analysis
| Aspect | Value |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
The Counter construction takes O(n). The sort takes O(n log n). Each comparison inside the sort calls the key function in O(1), so the total time is O(n log n). The space is O(n) for the frequency map (which stores at most n entries if all values are distinct).
The building blocks
Frequency counting with a hash map
Counting how often each element appears is one of the most common interview patterns. You scan the array once, incrementing a counter for each value. In Python, Counter does this for you, but the underlying idea is the same as a manual dictionary:
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
This same building block appears in Top K Frequent Elements, Sort Characters by Frequency, and many other problems. Any time a problem mentions "frequency," "count," or "how many times," you reach for this pattern.
Custom sort keys with tuples
Python's sort and sorted accept a key parameter. When you return a tuple, Python sorts lexicographically: it compares the first element of each tuple, and only uses the second element as a tiebreaker. Negating a numeric value flips its sort direction.
items.sort(key=lambda x: (primary_key(x), -secondary_key(x)))
This pattern is powerful because it lets you express multi-level sort orders in a single line. You do not need to write a custom comparator class or chain multiple sorts. Any time you need "sort by A, then by B in reverse," a tuple key with negation is the cleanest approach.
Edge cases
- All elements identical:
nums = [5, 5, 5]. Every element has the same frequency, so the tiebreaker sorts by value descending. The array stays[5, 5, 5]. - All elements unique:
nums = [3, 1, 2]. Every element has frequency 1, so the sort becomes purely by value descending:[3, 2, 1]. - Negative values:
nums = [-1, 1, -1, 1, 1]. The negation trick(-x)works correctly with negative numbers.-(-1)is1and-(1)is-1, so within the same frequency group,-1(value -1) sorts after1(value 1). The result is[-1, -1, 1, 1, 1]. - Single element:
nums = [7]. One element, frequency 1. The result is[7]. - Two elements tied on frequency:
nums = [2, 3, 1, 3, 2]. Both 2 and 3 have frequency 2, and 1 has frequency 1. The tiebreaker puts 3 before 2 (higher value first). Result:[1, 3, 3, 2, 2].
From understanding to recall
The solution is only three lines. Count frequencies, sort with a tuple key, return the result. It feels obvious once you see it. But during an interview, with time pressure and nerves, the details slip. Did you negate x or freq[x]? Does ascending frequency mean the key is freq[x] or -freq[x]? Is it nums.sort() or sorted(nums)?
These are recall gaps, not understanding gaps. Spaced repetition closes them. You write the solution from scratch, check it, and come back the next day. Then three days later. Then a week. After a few cycles, the (freq[x], -x) pattern fires automatically. You do not rederive it. You just write it.
Related posts
- Top K Frequent Elements - Frequency counting combined with a heap to find the k most common elements
- Sort Characters by Frequency - The same frequency-based sorting idea applied to characters in a string
- Relative Sort Array - Custom ordering where the sort order is defined by a second array