Problem Description

You are given an array of integers called nums. Your task is to sort this array according to specific rules:

1. Primary sorting rule: Sort the values based on their frequency (how many times they appear) in increasing order. This means values that appear less frequently should come before values that appear more frequently.

2. Secondary sorting rule: When multiple values have the same frequency, sort those values in decreasing order (larger values come before smaller values).

The function should return the sorted array following these rules.

For example, if you have an array like [1,1,2,2,2,3]:

• The frequency of 1 is 2
• The frequency of 2 is 3
• The frequency of 3 is 1

After sorting:

• 3 comes first (frequency 1)
• 1 comes next (frequency 2)
• 2 comes last (frequency 3)

When values have the same frequency, they should be arranged from largest to smallest. So the final result would be [3,1,1,2,2,2].

The solution uses Python's Counter to count frequencies and sorted() with a custom key function. The key (cnt[x], -x) sorts first by frequency cnt[x] in ascending order, then by the negative value -x to achieve descending order for the values themselves when frequencies are equal.

Intuition

The problem asks us to sort based on two criteria: frequency first, then value. This immediately suggests we need a way to count how often each number appears and then use custom sorting logic.

The key insight is recognizing this as a multi-level sorting problem. When we need to sort by multiple criteria in Python, we can use a tuple as the sorting key. Python sorts tuples by comparing elements from left to right - first by the first element, then by the second element if the first elements are equal, and so on.

For counting frequencies, a hash map (or Python's Counter) is the natural choice since we need to look up how many times each value appears. This gives us O(1) access to any number's frequency.

The trickier part is handling the secondary sorting rule. When frequencies are equal, we want larger numbers first (descending order). However, Python's default sort is ascending. To achieve descending order while keeping the primary sort ascending, we can use a clever trick: negate the values. Since -5 < -3 but 5 > 3, negating the values reverses their sort order.

This leads us to the solution: create a sorting key of (frequency, -value). The first element handles sorting by frequency in ascending order, and the second element (negated value) handles the tie-breaking in descending order. The sorted() function with this custom key does all the work in one pass, maintaining the relative positions as needed.

The beauty of this approach is its simplicity - we transform a complex two-condition sorting problem into a standard sort operation with a well-crafted key function.

Learn more about Sorting patterns.

Solution Approach

The implementation uses a straightforward approach with Python's built-in data structures and sorting capabilities.

Step 1: Count Frequencies We use Python's Counter from the collections module to count the frequency of each number in the array:

cnt = Counter(nums)

This creates a dictionary-like object where keys are the unique numbers from nums and values are their frequencies. For example, if nums = [1,1,2,2,2,3], then cnt would be {1: 2, 2: 3, 3: 1}.

Step 2: Custom Sorting The core of the solution is the sorting with a custom key function:

return sorted(nums, key=lambda x: (cnt[x], -x))

Let's break down how this works:

• sorted(nums, ...) iterates through each element in the original array
• For each element x, the lambda function creates a tuple (cnt[x], -x)
  • cnt[x] gives the frequency of that element
  • -x is the negated value of the element
• Python sorts based on this tuple key

How the Tuple Sorting Works: When Python compares two tuples, it follows lexicographic ordering:

1. First, compare the first elements (frequencies)
2. If frequencies are equal, compare the second elements (negated values)

For example, consider sorting [1, 1, 2, 2, 2, 3]:

• Element 1 gets key (2, -1)
• Element 2 gets key (3, -2)
• Element 3 gets key (1, -3)

Sorting these keys in ascending order:

• (1, -3) comes first (lowest frequency)
• (2, -1) comes second
• (3, -2) comes last (highest frequency)

This gives us the final sorted array: [3, 1, 1, 2, 2, 2].

The time complexity is O(n log n) due to sorting, and space complexity is O(n) for storing the frequency counter.

Example Walkthrough

Let's walk through a detailed example with the array [4, 4, 6, 6, 6, 1, 1, 2].

Step 1: Count Frequencies First, we count how many times each number appears:

• 1 appears 2 times
• 2 appears 1 time
• 4 appears 2 times
• 6 appears 3 times

So our frequency counter becomes: {4: 2, 6: 3, 1: 2, 2: 1}

Step 2: Assign Sorting Keys For each element in the original array, we create a sorting key (frequency, -value):

• 4 → (2, -4) (frequency is 2, negated value is -4)
• 4 → (2, -4)
• 6 → (3, -6) (frequency is 3, negated value is -6)
• 6 → (3, -6)
• 6 → (3, -6)
• 1 → (2, -1) (frequency is 2, negated value is -1)
• 1 → (2, -1)
• 2 → (1, -2) (frequency is 1, negated value is -2)

Step 3: Sort by Keys Now we sort these keys in ascending order:

1. (1, -2) - lowest frequency (1), so 2 comes first
2. (2, -4) - frequency 2, value 4
3. (2, -4) - same as above
4. (2, -1) - frequency 2, but -1 > -4, so 1 comes after 4
5. (2, -1) - same as above
6. (3, -6) - highest frequency (3), so 6 comes last
7. (3, -6) - same as above
8. (3, -6) - same as above

Notice how when frequencies are equal (both 4 and 1 have frequency 2), we sort by the second element of the tuple. Since -4 < -1, the value 4 (larger original value) comes before 1 (smaller original value), achieving descending order for values with the same frequency.

Final Result: [2, 4, 4, 1, 1, 6, 6, 6]

The array is now sorted with:

• 2 first (frequency 1)
• 4 and 1 next (both frequency 2, with 4 > 1 so 4 comes first)
• 6 last (frequency 3)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm consists of two main operations:

1. Creating a frequency counter using Counter(nums) takes O(n) time, where n is the length of the input array
2. Sorting the array using sorted() with a custom key takes O(n log n) time in the worst case

Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity: O(n)

The space usage comes from:

1. The Counter object cnt stores at most n key-value pairs (in the worst case where all elements are unique), requiring O(n) space
2. The sorted() function creates a new list containing all n elements, requiring O(n) space
3. The sorting algorithm itself (Timsort in Python) uses O(n) auxiliary space in the worst case

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Secondary Sort Correctly

A common mistake is to forget about the secondary sorting rule or implement it incorrectly. Developers might write:

Incorrect Implementation:

# Wrong: This sorts values in ascending order when frequencies are equal
sorted_nums = sorted(nums, key=lambda x: frequency_map[x])

This would sort by frequency alone, leaving the order of elements with the same frequency undefined or in their original order. For example, with [4, 5, 6, 5, 4, 3]:

• Frequencies: 3 appears 1 time, 6 appears 1 time, 4 appears 2 times, 5 appears 2 times
• Wrong output might be: [3, 6, 4, 4, 5, 5]
• Correct output should be: [6, 3, 5, 5, 4, 4] (larger values first when frequencies match)

Solution: Always include the secondary sort criterion using -x to ensure larger values come first when frequencies are equal:

sorted_nums = sorted(nums, key=lambda x: (frequency_map[x], -x))

2. Integer Overflow with Negation

When dealing with very large integers or the minimum integer value, negating them might cause issues in some programming languages. In Python, this isn't typically a problem due to arbitrary precision integers, but when translating to other languages like Java or C++, -x could overflow.

Solution for Other Languages: Instead of using negation, you can use a custom comparator or reverse the comparison logic:

# Alternative approach without negation
from functools import cmp_to_key

def compare(a, b):
    if frequency_map[a] != frequency_map[b]:
        return frequency_map[a] - frequency_map[b]  # Sort by frequency ascending
    return b - a  # Sort by value descending

sorted_nums = sorted(nums, key=cmp_to_key(compare))

3. Modifying the Original Array In-Place

If the problem requires preserving the original array, using nums.sort() instead of sorted(nums) would modify the input array:

Incorrect if original array must be preserved:

nums.sort(key=lambda x: (frequency_map[x], -x))
return nums  # Original array is modified

Solution: Use sorted() which returns a new sorted list without modifying the original:

return sorted(nums, key=lambda x: (frequency_map[x], -x))

4. Not Handling Empty Arrays

While the current solution handles empty arrays correctly (Counter and sorted both work with empty lists), it's good practice to explicitly check for edge cases:

Enhanced Solution:

def frequencySort(self, nums: List[int]) -> List[int]:
    if not nums:  # Explicit check for empty array
        return []
  
    frequency_map = Counter(nums)
    return sorted(nums, key=lambda x: (frequency_map[x], -x))