The “Sort Array by Increasing Frequency” problem on Leetcode provides an excellent opportunity to explore array manipulation and sorting algorithms in depth. It poses a dual challenge: first, you need to sort the elements based on their frequency, and second, for elements with the same frequency, you need to sort them based on their value. This multi-level sorting requirement makes the problem a rich ground for exploration and discussion.
In this detailed article, we will dissect the problem, delve into different approaches to solve it, discuss their time and space complexities, and implement the solutions in Python.
The problem statement is as follows:
Given an array of integers
nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
frequencySort([1,1,2,2,2,3]) # Output: [3,1,1,2,2,2]
Approach 1: Count and Custom Sort
- Count the frequency of each number in the array using a dictionary.
- Use Python’s built-in
sortedfunction with a custom key function that takes into account both frequency and value.
from typing import List from collections import Counter def frequencySort(nums: List[int]) -> List[int]: freq_map = Counter(nums) return sorted(nums, key=lambda x: (freq_map[x], -x))
The time complexity is O(n log n), where n is the length of the input list. This is primarily because of the sorting operation.
The space complexity is O(n) for storing the frequency map.
Approach 2: Bucket Sort
- Count the frequency of each number and store it in a dictionary.
- Create buckets based on frequencies and place numbers in their corresponding buckets.
- Sort each bucket individually, then concatenate them.
from typing import List from collections import Counter def frequencySort(nums: List[int]) -> List[int]: freq_map = Counter(nums) max_freq = max(freq_map.values()) buckets = [ for _ in range(max_freq + 1)] for num, freq in freq_map.items(): buckets[freq].append(num) for bucket in buckets: bucket.sort(reverse=True) sorted_nums =  for i, bucket in enumerate(buckets): for num in bucket: sorted_nums.extend([num] * i) return sorted_nums
The time complexity is O(n+k log k), where n is the number of elements in the list and k is the number of unique elements. This is because we need to sort each bucket.
The space complexity is O(n) for storing the frequency map and buckets.
The “Sort Array by Increasing Frequency” problem serves as an excellent platform to deepen our understanding of sorting algorithms and array manipulation. While the custom sort approach is simple and leverages Python’s powerful built-ins, the bucket sort approach provides an alternative that might be more efficient when the number of unique elements is small.