Sort Array by Increasing Frequency - Video Solutions

Problem Overview: Given an integer array, reorder the elements so numbers with lower frequency appear first. If two numbers have the same frequency, the larger number should come first. The output is simply the array sorted by these two rules.

Approach 1: Frequency Map and Sort (O(n log n) time, O(n) space)

The most direct solution counts how often each number appears using a hash map. After building the frequency map, sort the array using a custom comparator: first compare frequencies (ascending), and if they match, compare values (descending). Most languages allow sorting with a custom key or comparator, which makes this approach concise. The key insight is separating counting from ordering: the hash table gives O(1) lookups for frequency, while the sorting step applies the problem’s ordering rules. Overall complexity is dominated by sorting, giving O(n log n) time and O(n) extra space for the frequency map.

Approach 2: Bucket Sort Based on Frequency (O(n) time, O(n) space)

Since frequencies range from 1 to n, you can avoid comparison sorting. First count frequencies with a hash map. Then create buckets where index i stores numbers that appear exactly i times. Iterate through buckets from low frequency to high. Inside each bucket, sort numbers in descending order to satisfy the tie-breaking rule, then append each number freq times to the result. This transforms the problem into grouped processing rather than global sorting. Because each element is processed a constant number of times, the total complexity becomes O(n) time with O(n) space. This approach relies on properties of the array size and frequency bounds.

Recommended for interviews: The frequency map + sort approach is usually expected. It’s simple, readable, and easy to implement under time pressure. Interviewers mainly want to see that you identify the two sorting criteria and use a hash map to compute frequencies. Bucket sort shows deeper algorithmic thinking and improves the theoretical complexity to O(n), but it’s rarely required unless the interviewer explicitly asks for linear time.