DDSA Solutions

1636. Sort Array by Increasing Frequency

UnknownView on LeetCode
ArrayHash TableSortingCounting
Time: O(n log n)
Space: O(n)

Problem Overview

Sort the array by how often each value appears — higher frequency first.

Advertisement

Intuition

Sort the array by how often each value appears — higher frequency first. When two values tie in frequency, the larger value comes first. Count frequencies with a hash map, then sort with a custom comparator.

Algorithm

  1. 1Build frequency map: value → count.
  2. 2Sort nums with comparator: compare (-freq[a], -a) vs (-freq[b], -b).
  3. 3Negative freq sorts descending frequency; negative value breaks ties by larger value first.
  4. 4Return the sorted array.

Example Walkthrough

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

  1. 1.Frequencies: 3→2, 2→2, 1→1.
  2. 2.Tie on freq 2: 3 before 2 (larger value). Then 1.

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

Common Pitfalls

  • •Tie-break is by value descending, not ascending.
  • •Comparator must use frequency first, then value.
  • •O(n log n) from sorting; counting is O(n).
1636.cs
C#
// Approach: Count frequencies then sort by frequency ascending, value descending.
// Time: O(n log n) Space: O(n)

public class Solution {
    public int[] FrequencySort(int[] nums) {
        int[] cnt = new int[201];
        var t = new List<int>();

        foreach(int num in nums)
        {
            int v = num + 100;
            ++cnt[v];
            t.Add(v);
        }

        t.Sort((a, b) => cnt[a] == cnt[b] ? b - a : cnt[a] - cnt[b]);

        int[] ans = new int[nums.Length];

        for(int i = 0; i < t.Count; i++)
            ans[i] = t[i] - 100;

        return ans;
    }
}
Advertisement
Was this solution helpful?

Related Problems