Problem Description

Given an integer array nums, the task is to 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.

• Elements with lower frequency appear first.
• If two numbers have the same frequency, the larger number comes first.
• Return the sorted array as the result.

Example:
Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]

Constraints:

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

Thought Process

The problem asks us to sort an array based on the frequency of each element, with a specific tiebreaker: if two numbers occur the same number of times, the larger number should come first.

The brute-force way would be to count the frequency of each number, then repeatedly scan the array to pick the lowest-frequency numbers first, applying the tiebreaker as needed. However, this would be inefficient and repetitive.

Instead, we can leverage data structures that let us efficiently count frequencies (like a hash map or dictionary), and then use a custom sort function to handle the sorting rules. This reduces the problem to two main steps: counting and sorting.

This approach is much faster and easier to implement, especially with languages that support custom sorting logic.

Solution Approach

Let's break down the solution step by step:

1. Count Frequencies:
   • Use a hash map (or dictionary) to count how many times each element appears in nums.
2. Sort Using Custom Rules:
   • Sort the array with a custom comparator:
     • First, compare the frequency of two numbers. The one with lower frequency comes first.
     • If frequencies are equal, compare the numbers themselves. The larger number comes first.
3. Return the Sorted Array:
   • After sorting, return the new array as the result.

Design Justification: We use a hash map for O(1) frequency lookups, and a custom sort to handle the dual sorting criteria efficiently. This is much more optimal than repeatedly scanning the array for the next element to place.

Example Walkthrough

Let's walk through the example nums = [1,1,2,2,2,3]:

1. Count Frequencies:
   • 1: appears 2 times
   • 2: appears 3 times
   • 3: appears 1 time
2. Sort by Frequency, then Value:
   • 3 has frequency 1 (lowest), so it comes first.
   • 1 has frequency 2, 2 has frequency 3.
   • So, after 3, we place both 1s, then all 2s.

   Final sorted array: [3, 1, 1, 2, 2, 2]

If two numbers had the same frequency, the larger one would come first among them.

Time and Space Complexity

Brute-force Approach:

• Counting frequencies: O(n)
• Repeatedly finding the next element: O(n^2)
• Total: O(n^2)

• Counting frequencies using a hash map: O(n)
• Sorting with custom comparator: O(n log n)
• Total: O(n log n)
• Space: O(n) for the frequency map and the output array

The optimized approach is efficient and easily handles the problem's constraints.

Code Implementation

from collections import Counter

class Solution:
    def frequencySort(self, nums):
        freq = Counter(nums)
        # Sort by frequency ascending, then by value descending
        return sorted(nums, key=lambda x: (freq[x], -x))
      

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<int> frequencySort(std::vector<int>& nums) {
        std::unordered_map<int, int> freq;
        for (int n : nums) freq[n]++;
        std::sort(nums.begin(), nums.end(), [&](int a, int b) {
            if (freq[a] != freq[b]) return freq[a] < freq[b];
            return a > b;
        });
        return nums;
    }
};
      

import java.util.*;

class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums)
            freq.put(n, freq.getOrDefault(n, 0) + 1);
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, (a, b) -> {
            if (!freq.get(a).equals(freq.get(b)))
                return freq.get(a) - freq.get(b);
            return b - a;
        });
        for (int i = 0; i < nums.length; ++i)
            nums[i] = arr[i];
        return nums;
    }
}
      

var frequencySort = function(nums) {
    const freq = {};
    for (const n of nums) freq[n] = (freq[n] || 0) + 1;
    nums.sort((a, b) => {
        if (freq[a] !== freq[b]) return freq[a] - freq[b];
        return b - a;
    });
    return nums;
};
      

Summary

The "Sort Array by Increasing Frequency" problem is efficiently solved by counting element frequencies and then sorting with a custom comparator that prioritizes lower frequencies and, in case of ties, larger numbers. This approach leverages hash maps for fast counting and the language's built-in sorting for clarity and performance, making it both elegant and efficient.