Vultr DocsLatest Content

Sort Array by Increasing Frequency

Updated on 11 July, 2025
Sort Array by Increasing Frequency header image

Problem Statement

In this task, we are provided with an array of integers called nums. Our objective is to sort this array based on a specific criterion. Initially, the array should be arranged in increasing order according to the frequency of the values. If two numbers have the same frequency, however, they should be sorted in decreasing numerical order. The outcome should be the numerically sorted array based on these conditions.

Examples

Example 1

Input:

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

Output:

[3,1,1,2,2,2]

Explanation:

'3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2

Input:

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

Output:

[1,3,3,2,2]

Explanation:

'2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

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 <= 100
  • -100 <= nums[i] <= 100

Approach and Intuition

Let’s break down the sorting method mentioned in the problem statement through examples and the given constraints:

  1. Count Frequency:
    The first step is to determine how often each number appears in the array. This will involve creating a frequency map where the key is the number and the value is the count of occurrences in the array.

  2. Sort by Frequency:
    Once we have the frequency of each number, sort the numbers based on their frequency. Numbers with a lower frequency should come earlier in the array.

  3. Handle Same Frequency:
    If two numbers have the same frequency, we need a secondary rule. In such cases, numbers should be sorted in decreasing order. This means larger numbers come first if their frequency matches with another.

  4. Construct Result:
    After sorting based on the above rules, construct the array in the sorted order as per these rules.

Looking at the constraints provided:

  • The array length varies from 1 to 100, which means our sorting algorithm doesn't need to be highly optimized for extremely large datasets.
  • The value of numbers in the array ranges from -100 to 100. This limited range suggests that frequency counting and sorting can be handled efficiently.

Examples Analysis:

  • In the first example, nums = [1,1,2,2,2,3], after sorting by frequency then by value where necessary, the least frequent number (3) comes first, followed by the more frequent numbers.
  • The third example introduces negative numbers and it confirms that the sorting rules apply universally to any integer values. The array nums = [-1,1,-6,4,5,-6,1,4,1] sorts the numbers primarily by their frequency counts and then by their values where frequencies tie.

This method ensures an orderly and intuitive arrangement of numbers catering both to how common they are and their relative magnitude.

Solutions

  • C++
cpp 
class Solution {
public:
    vector<int> sortFrequency(vector<int>& elements) {
        unordered_map<int, int> count;
        for (int element : elements) {
            count[element]++;
        }
    
        sort(elements.begin(), elements.end(), [&](int x, int y) {
            if (count[x] == count[y]) {
                return x > y;
            }
            return count[x] < count[y];
        });
    
        return elements;
    }
};

Sort an array in C++ by increasing frequency of elements using a hash map and a custom comparator with the sort function. Begin by creating an unordered_map to maintain a count of each element in the array. Iterate through the array to populate this map. Then, use the sort function from the Standard Library, passing in a custom comparator lambda function. This function sorts based on frequency, and if frequencies are the same, it sorts based on value in descending order. After sorting, return the modified array. This approach ensures that the elements are sorted first by their frequency in ascending order and then by their value in descending order if their frequencies match.

  • Java
java 
class Solution {
    
    public int[] sortFrequency(int[] elements) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int element : elements) {
            count.put(element, count.getOrDefault(element, 0) + 1);
        }
    
        Integer[] boxedElements = new Integer[elements.length];
        for (int i = 0; i < elements.length; i++) {
            boxedElements[i] = elements[i];
        }
    
        Arrays.sort(boxedElements, (x, y) -> {
            if (count.get(x).equals(count.get(y))) {
                return Integer.compare(y, x);
            }
            return Integer.compare(count.get(x), count.get(y));
        });
    
        for (int i = 0; i < elements.length; i++) {
            elements[i] = boxedElements[i];
        }
    
        return elements;
    }
}

The provided Java solution focuses on solving the problem of sorting an array of integers by the frequency of each element, with a fallback to sorting by the element values in descending order if frequencies are the same. Follow this process to understand how the given code achieves this:

  1. Create a frequency map to count occurrences of each element using a HashMap.
  2. Convert the primitive int array to an Integer array to utilize custom sorting functionality.
  3. Sort the Integer array based on the criteria:
    • Primary sort is by frequency of elements in ascending order.
    • If two elements have the same frequency, sort them by their value in descending order.
  4. After sorting the boxed Integer array, transfer the sorted values back into the original int array.
  5. Return the modified array, now sorted according to the specified criteria.

This implementation efficiently leverages Java's Collection utilities such as HashMap for counting and Arrays.sort with a lambda expression to define custom sorting behavior.

  • Python
python 
from collections import Counter
    
class Solution:
    def sort_by_frequency(self, items: List[int]) -> List[int]:
        frequency_count = Counter(items)
        return sorted(items, key=lambda item: (frequency_count[item], -item))

The provided Python solution tackles the problem of sorting an array by increasing frequency of its elements. The approach leverages the collections.Counter from Python’s standard library to efficiently count the frequency of each element in the input list.

After computing the frequency of each item, the solution uses Python's sorted() function with a custom key. This custom key is a lambda function that sorts primarily by the frequency of the items and, in case of ties (i.e., when two elements have the same frequency), it sorts by the value of the items in decreasing order (achieved with -item).

Follow these steps to fully understand and implement the approach:

  1. Import the Counter class from the collections module.
  2. Define a solution class and a method sort_by_frequency, which accepts a list of integers.
  3. Inside the method, create a frequency count of list items using Counter.
  4. Return the list sorted by frequency using sorted() with a custom key defined by a lambda function that takes item frequencies into account.

This method ensures that the list is sorted first by the frequency of the items in ascending order and then by the item values in descending order in the case of frequency ties.

Comments

No comments yet.