Difficulty: Easy | Acceptance: 80.80% | Paid: No Topics: Array, Hash Table, Sorting
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.
Return the sorted array.
- Examples
- Constraints
- Approach 1: Sorting with Custom Comparator
- Approach 2: Bucket Sort
- Approach 3: Brute Force Selection
Examples
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.
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.
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 1: Sorting with Custom Comparator
Intuition We can count the frequency of each number using a hash map, then sort the array using a custom comparator that sorts by frequency first, and by value in descending order for ties.
Steps
- Count the frequency of each number in the array.
- Sort the array using a custom comparator:
- If frequencies are different, sort by increasing frequency.
- If frequencies are the same, sort by decreasing value.
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
freq = collections.Counter(nums)
return sorted(nums, key=lambda x: (freq[x], -x))
Complexity
- Time: O(n log n)
- Space: O(n)
- Notes: The sorting step dominates the time complexity.
Approach 2: Bucket Sort
Intuition Since the range of values and the length of the array are limited, we can use bucket sort. We create buckets where the index represents the frequency, and each bucket contains numbers with that frequency. We then iterate through the buckets in increasing order of frequency, and within each bucket, sort numbers in decreasing order.
Steps
- Count the frequency of each number.
- Create an array of buckets (lists) where the index corresponds to the frequency.
- Populate the buckets with numbers.
- Iterate through the buckets from index 1 to n.
- For each bucket, sort the numbers in descending order and add them to the result array, repeating each number according to its frequency.
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
freq = collections.Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
res = []
for i in range(len(buckets)):
if buckets[i]:
buckets[i].sort(reverse=True)
for num in buckets[i]:
res.extend([num] * i)
return res
Complexity
- Time: O(n + k log k) where k is the range of values (max 201).
- Space: O(n)
- Notes: This approach can be more efficient than sorting if the range of frequencies is small.
Approach 3: Brute Force Selection
Intuition Repeatedly scan the remaining elements to find the one with the lowest frequency (and highest value if tied), add it to the result, and remove it from the list of available elements.
Steps
- Count the frequency of each number.
- Initialize an empty result array.
- While the input array is not empty:
- Find the element with the minimum frequency.
- If there is a tie, choose the element with the maximum value.
- Append this element to the result.
- Remove this element from the input array.
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
freq = collections.Counter(nums)
res = []
while nums:
candidate = nums[0]
for x in nums:
if freq[x] < freq[candidate] or (freq[x] == freq[candidate] and x > candidate):
candidate = x
res.append(candidate)
nums.remove(candidate)
return res
Complexity
- Time: O(n²)
- Space: O(n)
- Notes: This approach is inefficient for large inputs but demonstrates the logic clearly.