Sort Array by Increasing Frequency

Sort Array by Increasing Frequency

What is this problem about?

The "Sort Array by Increasing Frequency" problem asks you to rearrange an array based on two criteria:

1. Primary: The frequency of the elements. Elements that appear fewer times should come first.
2. Secondary: The value of the elements. If two elements have the same frequency, they should be sorted in descending order.

This is a great exercise in multi-level sorting. You must first count how many times each number appears and then use those counts to reorder the original array.

Why is this asked in interviews?

Companies from Goldman Sachs to Adobe use this interview question to test a candidate's ability to use Hash Tables (for counting) and custom sorting logic. It’s a practical problem that mimics real-world data processing tasks where you often need to sort by one attribute and then "break ties" using another. It evaluates whether you can write clean, concise code for multi-step data transformations.

Algorithmic pattern used

The pattern involves a two-step approach:

1. Frequency Counting: Use a Hash Table (or a dictionary) to store the frequency of each element in the array.
2. Custom Sorting: Sort the array using a comparator that first compares the frequencies of two numbers from the hash table. If the frequencies are equal, it compares the values themselves in descending order.

Example explanation

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

1. Count frequencies: {1: 2, 2: 3, 3: 1}.
2. Sort elements:
   • 3 has frequency 1 (lowest), so it comes first.
   • 1 has frequency 2, it comes next.
   • 2 has frequency 3, it comes last. Result: [3, 1, 1, 2, 2, 2]. If the input was [1, 1, 2, 2, 3], frequencies are {1: 2, 2: 2, 3: 1}.

• 3 comes first (freq 1).
• 1 and 2 both have freq 2. Since 2 > 1, 2 comes before 1 (descending tie-break). Result: [3, 2, 2, 1, 1].

Common mistakes candidates make

A common mistake is forgetting the second sorting criteria (descending order for tie-breaks). Another error is inefficiently re-counting frequencies inside the sort function, which leads to $O(N^2 \log N)$ or worse performance. You should always pre-calculate the frequencies in $O(N)$ time. Some candidates also struggle with the syntax for complex sorting, especially in languages like Java or C++ where multi-level comparators can be verbose.

Interview preparation tip

To master the "Sort Array by Increasing Frequency interview question," practice using frequency maps and custom sorting keys. In Python, you can use sort(key=lambda x: (freq[x], -x)). In other languages, learn how to use thenComparing or multiple if statements in a comparator. Understanding how to combine data structures like maps and lists effectively is a key skill for any software engineer.