Sort Array by Increasing Frequency — Custom Comparator with Frequency Counting

Problem Statement#

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order of value.

Constraints:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

Examples:

Example 1:
Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' appears once, '1' twice, '2' three times. Sort ascending by freq.
 
Example 2:
Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '1' appears once, '2' and '3' both appear twice.
  For freq=2: tie → sort by value descending → 3 before 2.
 
Example 3:
Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Why This Problem Matters#

Sort Array by Increasing Frequency is an easy-to-medium problem that appears deceptively simple but tests a fundamental skill: constructing composite sort keys. Many real-world sorting problems require ordering by multiple criteria simultaneously, and understanding how to express this as a single comparator or key function is essential.

Amazon and Google use variations of this problem in screening rounds because it quickly reveals whether a candidate understands their language's sort API deeply. In Python, the key parameter allows elegant multi-criteria sorting. In JavaScript, a custom comparator function must handle all criteria in a single comparison. Candidates who can't implement this cleanly often struggle with more complex sort-based problems.

The problem also teaches frequency counting as a preprocessing step — a pattern that appears throughout algorithm design. Before you can sort by frequency, you must compute frequencies. The Counter class in Python and Map in JavaScript are tools every interviewer expects you to use fluently.

While the constraints here are small (n ≤ 100), the technique scales: the same approach applies to "Top K Frequent Elements" (n ≤ 10^6), "Sort Characters by Frequency," and any other problem requiring frequency-ordered output.

The Core Insight#

The key insight is that Python's sorted (and JavaScript's Array.sort) accept a composite key: sort first by frequency ascending, then by value descending as a tiebreaker. In Python, this is expressed as a tuple key (frequency, -value):

• Sort by frequency ascending → first element of tuple, ascending.
• Sort by value descending → second element of tuple, -value ascending (negating reverses direction).

In JavaScript, a comparator function (a, b) => freq[a] !== freq[b] ? freq[a] - freq[b] : b - a expresses the same logic.

Once you have the frequency map, the actual sorting is one line. The problem is really about knowing your sorting API well enough to express two-level sort criteria cleanly.

Visual Dry Run#

nums = [2, 3, 1, 3, 2]
 
Step 1: Count frequencies.
  count = {2: 2, 3: 2, 1: 1}
 
Step 2: Sort with key = (frequency, -value).
  Element 1: key = (1, -1) = (1, -1)
  Element 2: key = (2, -2)
  Element 3: key = (2, -3)
 
Step 3: Sort tuples:
  (1, -1) < (2, -3) < (2, -2)
  → [1, 3, 3, 2, 2]
 
Step 4: Expand each element by its frequency.
  1 appears 1 time: [1]
  3 appears 2 times: [3, 3]
  2 appears 2 times: [2, 2]
  Result: [1, 3, 3, 2, 2]. ✓

Solution (Optimal)#

from collections import Counter
 
def frequencySort(nums):
    count = Counter(nums)
    
    # Sort by (frequency ascending, value descending)
    # Using key=(count[x], -x) achieves both criteria
    return sorted(nums, key=lambda x: (count[x], -x))

function frequencySort(nums) {
    // Build frequency map
    const count = new Map();
    for (const n of nums) {
        count.set(n, (count.get(n) || 0) + 1);
    }
    
    // Sort by frequency ascending, then by value descending
    return [...nums].sort((a, b) => {
        if (count.get(a) !== count.get(b)) {
            return count.get(a) - count.get(b);  // frequency ascending
        }
        return b - a;  // value descending on tie
    });
}

Complexity Analysis:

• Time: O(n log n) — building the frequency map is O(n); sorting is O(n log n)
• Space: O(n) — frequency map and sorted output array

Common Mistakes#

• Sorting by value ascending instead of descending on ties. The problem specifies that for equal frequencies, sort by value descending. Using +x instead of -x gives wrong results.
• Modifying the original array. In Python, sorted returns a new list; list.sort() modifies in place. Use sorted unless you're sure in-place is acceptable. In JavaScript, [...nums].sort(...) creates a copy.
• Building the frequency map incorrectly. Counter(nums) in Python handles all cases. In JavaScript, use a Map or plain object — be careful with negative numbers as object keys (they stringify to negative strings, which still works but is ugly).
• Using a heap unnecessarily. This problem doesn't need a heap — it's a sort with a custom comparator. A heap would add complexity without benefit for this problem size.
• Forgetting the comparator handles individual elements. sorted(nums, key=...) applies the key to each element and sorts the elements. Don't confuse sorting the unique values with sorting the full array.

Follow-up Questions#

1. What if you want to sort in decreasing frequency order with ties broken by value ascending? Change the key to (-count[x], x).
2. What if the array has 10^6 elements instead of 100? Does the algorithm still work? What's the bottleneck?
3. Implement a heap-based solution that achieves the same result. When would a heap be preferable over sorting?
4. What if you need to return only the k most frequent elements in sorted order? (LeetCode 347 — Top K Frequent Elements.)
5. Can you solve this in O(n) using counting sort, given that values are in [-100, 100]?
6. What is the stable sort guarantee, and does it matter here given the two-level sort key?

Related Problems#

• LeetCode 451 — Sort Characters by Frequency: Sort string characters by frequency descending; same pattern, just strings.
• LeetCode 347 — Top K Frequent Elements: Find k most frequent; heap or bucket sort.
• LeetCode 692 — Top K Frequent Words: Frequency sort with lexicographic tiebreaking.
• LeetCode 1636 — Sort Array by Increasing Frequency: This exact problem.
• LeetCode 791 — Custom Sort String: Sort using a custom priority order; related custom comparator.
• LeetCode 539 — Minimum Time Difference: Sort timestamps to find minimum difference; custom sort application.

Key Takeaways#

• Build a frequency map first (Counter in Python, Map in JavaScript), then sort with a composite key
• Python composite sort key: lambda x: (count[x], -x) — frequency ascending, value descending on ties
• JavaScript comparator: (a, b) => count[a] !== count[b] ? count[a] - count[b] : b - a
• The (freq, -value) tuple key elegantly handles both sorting criteria in a single sort pass
• Negate the value for descending tiebreaking in Python — this is the standard trick for multi-criteria sorts
• Time O(n log n), space O(n) — frequency map O(n), sort O(n log n)
• This frequency-count-then-sort pattern is the foundation for LC 451, LC 347, LC 692, and many frequency-based problems