Problem of The Day: Sort Array by Increasing Frequency

Problem Statement

Intuition

When I first looked at the problem, I thought about how we can use a frequency map to count the occurrences of each number in the list. By doing so, we can then organize these numbers based on their frequency and sort them accordingly. My goal is to sort the numbers in ascending order based on their frequency, and in case of a tie, sort the numbers with the same frequency in descending order.

Approach

1. Frequency Map: First, I will create a frequency map to count how often each number appears in the input list.
2. Group by Frequency: Next, I will create another map where the keys are frequencies and the values are lists of numbers that appear with that frequency.
3. Sort and Arrange: Then, I will sort the keys of this frequency map in ascending order. For each frequency, I will sort the corresponding list of numbers in descending order.
4. Construct Result: Finally, I will construct the result list by appending each number, repeated according to its frequency, to the result list.

Complexity

• Time complexity: (O(n \log n))

  • Constructing the frequency map takes (O(n)) time.
  • Sorting the frequency keys and sorting the numbers for each frequency take (O(n \log n)) time.
  • Constructing the result list takes (O(n)) time.

• Space complexity: (O(n))

  • The space required for the frequency map and the grouped frequency list is (O(n)).
  • The result list also requires (O(n)) space.

Code

from collections import defaultdict
from typing import List

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1

        freq_list = defaultdict(list)
        for k, v in freq.items():
            freq_list[v].append(k)

        freq_order = sorted(freq_list.keys())
        res = []
        for cnt in freq_order:
            reverse_order = sorted(freq_list[cnt], reverse=True)
            for x in reverse_order:
                res.extend([x] * cnt)

        return res

Editorial

Approach: Customized Sorting

from collections import Counter


class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freq = Counter(nums)
        return sorted(nums, key=lambda x: (freq[x], -x))