Sort Array by Increasing Frequency

Easy
366.

Sort Array by Increasing Frequency

Sort Array by Increasing Frequency is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Adobe interviews.

Given an array of integers nums, sort it in increasing order of the frequency of the values.

Values that occur equally often are sorted in decreasing order of value.

Example 1

Input
nums = [1,1,2,2,2,3]
Output
[3,1,1,2,2,2]
Explanation
3 occurs once, 1 twice, 2 three times.

Example 2

Input
nums = [2,3,1,3,2]
Output
[1,3,3,2,2]
Explanation
2 and 3 both occur twice, so the larger value comes first.

Example 3

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

Constraints

  • 1 <= nums.length <= 40
  • -100 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var frequencySort = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort Array by Increasing Frequency — Problem & Solution

Sort Array by Increasing Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sort Array by Increasing Frequency is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Sorting
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of integers nums, sort it in increasing order of the frequency of the values.

Values that occur equally often are sorted in decreasing order of value.

Example 1

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: 3 occurs once, 1 twice, 2 three times.

Example 2

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: 2 and 3 both occur twice, so the larger value comes first.

Example 3

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

Constraints

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

Hints for Sort Array by Increasing Frequency

  1. Hint 1

    Count the occurrences first, then sort with a comparator that reads those counts.

  2. Hint 2

    The primary key is the count ascending; the secondary key is the value descending.

  3. Hint 3

    Sorting the original array (not the distinct values) keeps every copy in the output.

How to solve Sort Array by Increasing Frequency

Count occurrences, then sort the original array by (count ascending, value descending).

Approach

  1. Count each value.
  2. Sort nums with key (count[x], -x).

Why it works

Sorting the array itself keeps every copy, and the composite key encodes both rules.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Sorting the distinct values and expanding also works but is more bookkeeping.

Reference solution

Python

def frequencySort(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    return sorted(nums, key=lambda x: (count[x], -x))

Java

public static int[] frequencySort(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    Integer[] boxed = new Integer[nums.length];
    for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];
    Arrays.sort(boxed, (a, b) -> {
        int ca = count.get(a), cb = count.get(b);
        if (ca != cb) return ca - cb;
        return b - a;
    });
    int[] out = new int[nums.length];
    for (int i = 0; i < nums.length; i++) out[i] = boxed[i];
    return out;
}

C++

vector<int> frequencySort(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    vector<int> out = nums;
    sort(out.begin(), out.end(), [&](int a, int b) {
        int ca = count[a], cb = count[b];
        if (ca != cb) return ca < cb;
        return a > b;
    });
    return out;
}

JavaScript

var frequencySort = function(nums) {
    const count = new Map();
    for (let i = 0; i < nums.length; i++) {
        count.set(nums[i], (count.get(nums[i]) || 0) + 1);
    }
    return nums.slice().sort(function(a, b) {
        const ca = count.get(a), cb = count.get(b);
        if (ca !== cb) return ca - cb;
        return b - a;
    });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets