Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sort Array by Increasing Frequency

EASYProblemSolveExternal Links

Description

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. That is, elements that appear fewer times should come first, and elements that appear more times should come later.

If multiple values have the same frequency, sort those values in decreasing order (the larger value comes first among values with equal frequency).

Return the sorted array.

In simpler terms: count how many times each number appears, then rearrange the array so that rare numbers come before common numbers. Among numbers that are equally common, put the bigger number first.

Examples

Example 1

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

Output: [3, 1, 1, 2, 2, 2]

Explanation:

  • 3 appears 1 time (frequency = 1)
  • 1 appears 2 times (frequency = 2)
  • 2 appears 3 times (frequency = 3)

Sorted by increasing frequency: 3 (freq 1) → 1, 1 (freq 2) → 2, 2, 2 (freq 3).

Example 2

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

Output: [1, 3, 3, 2, 2]

Explanation:

  • 1 appears 1 time (frequency = 1)
  • 2 appears 2 times (frequency = 2)
  • 3 appears 2 times (frequency = 2)

1 comes first (lowest frequency). Then 3 and 2 both have frequency 2, but since we sort by decreasing value for ties, 3 (larger) comes before 2 (smaller). Result: [1, 3, 3, 2, 2].

Example 3

Input: nums = [-1, 1, -6, 4, 5, -6, 1, 4, 1]

Output: [5, -1, 4, 4, -6, -6, 1, 1, 1]

Explanation:

  • 5 appears 1 time, -1 appears 1 time (frequency = 1 each)
  • 4 appears 2 times, -6 appears 2 times (frequency = 2 each)
  • 1 appears 3 times (frequency = 3)

Frequency-1 elements come first. Among them, 5 > -1, so 5 comes before -1. Then frequency-2 elements: 4 > -6, so 4, 4 comes before -6, -6. Finally, frequency-3 element: 1, 1, 1.

Constraints

  • 1 ≤ nums.length ≤ 100
  • -100 ≤ nums[i] ≤ 100

Editorial

Brute Force

Intuition

The most natural approach is to directly compute the frequency of each element by scanning the entire array for each distinct value, and then use a simple sorting method (like selection sort or bubble sort) where we compare elements based on their computed frequencies.

Think of it like organizing a deck of playing cards by how many duplicates you have. You go through the deck once for each distinct card face to count duplicates, then you rearrange the deck so cards with fewer copies come first. For cards that have the same number of copies, you put the higher-valued card first.

For each pair of elements during the sort, we re-count their frequencies by scanning the array, then use those counts to decide their relative order. This repeated counting is what makes the brute force slow.

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 3, 2]:

Step 1: We need to sort by frequency. First, determine the frequency of each element by scanning the entire array for each distinct value:

  • Scan for 2: appears at indices 0, 4 → freq(2) = 2
  • Scan for 3: appears at indices 1, 3 → freq(3) = 2
  • Scan for 1: appears at index 2 → freq(1) = 1

Step 2: Now we sort. Consider each pair. Compare element 2 (freq 2) with element 3 (freq 2). Same frequency, so compare values: 3 > 2, so 3 comes first (decreasing order for ties).

Step 3: Compare element 1 (freq 1) with element 2 (freq 2). freq(1) < freq(2), so 1 comes first.

Step 4: Compare element 1 (freq 1) with element 3 (freq 2). freq(1) < freq(3), so 1 comes first.

Step 5: Arranging by the custom comparison: 1 (freq 1), then 3, 3 (freq 2, value 3), then 2, 2 (freq 2, value 2).

Step 6: Result = [1, 3, 3, 2, 2].

Brute Force — Counting Frequencies Then Sorting — Watch how we count frequencies by scanning the array for each value, then rearrange elements by increasing frequency and decreasing value for ties.

Algorithm

  1. For each element in the array, count its frequency by scanning the entire array (O(n) per element)
  2. Sort the array using a comparison-based sort where the comparator:
    a. Compares frequencies — element with lower frequency comes first
    b. If frequencies are equal, the element with higher value comes first
  3. Return the sorted array

Code

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        int n = nums.size();
        
        // Bubble sort using custom comparison
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // Count frequency of nums[j]
                int freqJ = 0;
                for (int k = 0; k < n; k++) {
                    if (nums[k] == nums[j]) freqJ++;
                }
                // Count frequency of nums[j+1]
                int freqJ1 = 0;
                for (int k = 0; k < n; k++) {
                    if (nums[k] == nums[j + 1]) freqJ1++;
                }
                // Compare: lower freq first, if equal then higher value first
                bool shouldSwap = false;
                if (freqJ > freqJ1) {
                    shouldSwap = true;
                } else if (freqJ == freqJ1 && nums[j] < nums[j + 1]) {
                    shouldSwap = true;
                }
                if (shouldSwap) {
                    swap(nums[j], nums[j + 1]);
                }
            }
        }
        
        return nums;
    }
};
class Solution:
    def frequencySort(self, nums: list[int]) -> list[int]:
        n = len(nums)
        
        # Bubble sort using custom comparison
        for i in range(n - 1):
            for j in range(n - i - 1):
                # Count frequency of nums[j] and nums[j+1]
                freq_j = sum(1 for x in nums if x == nums[j])
                freq_j1 = sum(1 for x in nums if x == nums[j + 1])
                
                # Lower frequency first; if equal, higher value first
                should_swap = False
                if freq_j > freq_j1:
                    should_swap = True
                elif freq_j == freq_j1 and nums[j] < nums[j + 1]:
                    should_swap = True
                
                if should_swap:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        
        return nums
class Solution {
    public int[] frequencySort(int[] nums) {
        int n = nums.length;
        
        // Bubble sort using custom comparison
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // Count frequency of nums[j]
                int freqJ = 0;
                for (int k = 0; k < n; k++) {
                    if (nums[k] == nums[j]) freqJ++;
                }
                // Count frequency of nums[j+1]
                int freqJ1 = 0;
                for (int k = 0; k < n; k++) {
                    if (nums[k] == nums[j + 1]) freqJ1++;
                }
                // Compare: lower freq first, if equal then higher value first
                boolean shouldSwap = false;
                if (freqJ > freqJ1) {
                    shouldSwap = true;
                } else if (freqJ == freqJ1 && nums[j] < nums[j + 1]) {
                    shouldSwap = true;
                }
                if (shouldSwap) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        
        return nums;
    }
}

Complexity Analysis

Time Complexity: O(n³)

Bubble sort makes O(n²) comparisons. For each comparison, we scan the array once to count the frequency of each of the two elements being compared, costing O(n) per comparison. Total: O(n²) × O(n) = O(n³). For n = 100, this is about 10^6 operations, which is manageable for this problem's constraints but not elegant.

Space Complexity: O(1)

We sort in place and use only a few integer variables. No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force recounts frequencies during every comparison in the sort. Since bubble sort makes O(n²) comparisons and each frequency count takes O(n), we end up with O(n³) time.

The fundamental waste is recomputing the same frequency over and over. The frequency of any element never changes, so counting it once and storing it is sufficient. If we precompute all frequencies in a single pass using a hash map, each subsequent comparison in the sort becomes O(1) instead of O(n).

This reduces the overall time to O(n log n) — the cost of the sort itself — because frequency lookups are now constant time.

Optimal Approach - Hash Map + Custom Sort

Intuition

The optimal approach separates the problem into two clear phases:

Phase 1: Count frequencies. Walk through the array once and record how many times each number appears using a hash map (dictionary). This takes O(n) time.

Phase 2: Sort with a custom comparator. Use an efficient sorting algorithm (like the language's built-in sort, which runs in O(n log n)) with a custom comparison function that:

  • First compares by frequency: lower frequency comes first
  • On tie (same frequency): larger value comes first (decreasing order)

Think of it like organizing files on your desk. First, you quickly count how many pages are in each folder (one pass through). Then you arrange the folders — those with fewer pages go to the front. If two folders have the same page count, you put the one with the higher file number first.

Because hash map lookups are O(1), each comparison during the sort is O(1), making the sort itself O(n log n). Combined with the O(n) counting phase, total time is O(n log n).

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 3, 2]:

Step 1: Build frequency map. Scan the array:

  • nums[0] = 2 → freq = {2: 1}
  • nums[1] = 3 → freq = {2: 1, 3: 1}
  • nums[2] = 1 → freq = {2: 1, 3: 1, 1: 1}
  • nums[3] = 3 → freq = {2: 1, 3: 2, 1: 1}
  • nums[4] = 2 → freq = {2: 2, 3: 2, 1: 1}

Step 2: Sort using custom comparator. For elements a and b:

  • If freq[a] ≠ freq[b]: element with lower freq comes first
  • If freq[a] == freq[b]: element with higher value comes first

Step 3: Compare 2 (freq 2) and 3 (freq 2): same frequency → 3 > 2, so 3 before 2.

Step 4: Compare 1 (freq 1) and 3 (freq 2): freq 1 < freq 2 → 1 before 3.

Step 5: Compare 1 (freq 1) and 2 (freq 2): freq 1 < freq 2 → 1 before 2.

Step 6: Final sorted order: [1, 3, 3, 2, 2].

Hash Map + Custom Sort — Building Frequencies Then Sorting — Watch how we build a frequency map in one pass, then use it as a lookup table during sorting to achieve O(n log n) total time.

Algorithm

  1. Build a frequency map: traverse the array once, counting occurrences of each value
  2. Sort the array using a custom comparator:
    • For two elements a and b:
      • If freq[a] ≠ freq[b]: return freq[a] < freq[b] (lower frequency first)
      • If freq[a] == freq[b]: return a > b (higher value first)
  3. Return the sorted array

Code

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        // Step 1: Build frequency map
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        // Step 2: Sort with custom comparator
        sort(nums.begin(), nums.end(), [&freq](int a, int b) {
            if (freq[a] != freq[b]) {
                return freq[a] < freq[b]; // lower frequency first
            }
            return a > b; // higher value first for same frequency
        });
        
        return nums;
    }
};
class Solution:
    def frequencySort(self, nums: list[int]) -> list[int]:
        # Step 1: Build frequency map
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        
        # Step 2: Sort with custom key
        # Sort by (frequency ascending, value descending)
        nums.sort(key=lambda x: (freq[x], -x))
        
        return nums
class Solution {
    public int[] frequencySort(int[] nums) {
        // Step 1: Build frequency map
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Sort with custom comparator
        // Need to convert to Integer[] for custom comparator
        Integer[] boxed = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            boxed[i] = nums[i];
        }
        
        Arrays.sort(boxed, (a, b) -> {
            if (!freq.get(a).equals(freq.get(b))) {
                return freq.get(a) - freq.get(b); // lower frequency first
            }
            return b - a; // higher value first for same frequency
        });
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = boxed[i];
        }
        
        return nums;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Building the frequency map takes O(n) — one pass through the array with O(1) hash map operations per element. Sorting takes O(n log n) with each comparison being O(1) because frequency lookups from the hash map are constant time. Total: O(n) + O(n log n) = O(n log n).

Space Complexity: O(n)

The frequency map stores at most n entries (one per distinct element). The sorting algorithm may also use O(log n) stack space internally. Total extra space: O(n).