1636. Sort Array by Increasing Frequency LeetCode Solution
In this guide, you will get 1636. Sort Array by Increasing Frequency LeetCode Solution with the best time and space complexity. The solution to Sort Array by Increasing Frequency problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Sort Array by Increasing Frequency
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.
Example 1:
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.
Example 2:
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.
1636. Sort Array by Increasing Frequency LeetCode Solution in C++
struct T {
int num;
int freq;
};
class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
vector<int> ans;
auto compare = [](const T& a, const T& b) {
return a.freq == b.freq ? a.num < b.num : a.freq > b.freq;
};
priority_queue<T, vector<T>, decltype(compare)> heap(compare);
unordered_map<int, int> count;
for (const int num : nums)
++count[num];
for (const auto& [num, freq] : count)
heap.emplace(num, freq);
while (!heap.empty()) {
const auto [num, freq] = heap.top();
heap.pop();
for (int i = 0; i < freq; ++i)
ans.push_back(num);
}
return ans;
}
}; /* code provided by PROGIEZ */
1636. Sort Array by Increasing Frequency LeetCode Solution in Java
class Solution {
public int[] frequencySort(int[] nums) {
record T(int num, int freq) {}
int[] ans = new int[nums.length];
int ansIndex = 0;
Map<Integer, Integer> count = new HashMap<>();
Queue<T> heap = new PriorityQueue<>((a, b) //
-> a.freq == b.freq ? Integer.compare(b.num, a.num)
: Integer.compare(a.freq, b.freq));
for (final int num : nums)
count.merge(num, 1, Integer::sum);
for (Map.Entry<Integer, Integer> entry : count.entrySet())
heap.offer(new T(entry.getKey(), entry.getValue()));
while (!heap.isEmpty()) {
final int num = heap.peek().num;
final int freq = heap.poll().freq;
for (int i = 0; i < freq; ++i)
ans[ansIndex++] = num;
}
return ans;
}
} // code provided by PROGIEZ
1636. Sort Array by Increasing Frequency LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class T:
num: int
freq: int
def __lt__(self, other):
if self.freq == other.freq:
return self.num > other.num
return self.freq < other.freq
class Solution:
def frequencySort(self, nums: list[int]) -> list[int]:
ans = []
heap = []
for num, freq in collections.Counter(nums).items():
heapq.heappush(heap, T(num, freq))
while len(heap) > 0:
num = heap[0].num
freq = heapq.heappop(heap).freq
ans.extend([num] * freq)
return ans # code by PROGIEZ
