1636.Sort Array by Increasing Frequency

Link: 1636. Sort Array by Increasing Frequency

Question

Restate the problem

Give an integer array nums, sort the array so that lower frequency comes first. if frequency is the same, return the larger value. Return the sorted array.

---

Method 1 - hashmap + heap
Method 2 - hashmap + sort

Method - built-in sort

Approach

Count the frequency of each number with a hash map / Counter, then sort nums using a custom key: (frequency[x], -x)

Complexity

• Time complexity is O($nlogn$)
• Space Complexity is O(n)

Edge Cases

• Negative numbers / zero

Code

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

Method 2 - heap

Complexity

• Time Complexity: O(n + k log k) (Counter + heap ops + output expansion)
  • k is unique values
• Space Complexity: O(k) heap + O(n) output

Code

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freq = Counter(nums)
        heap = []
        
        # time is O(nlogn)
        for num, count in freq.items(): # O(n)
            heapq.heappush(heap, (count, -num)) # O(logn)
        
        res = []
        while heap:
            freq, num = heapq.heappop(heap)
            for _ in range(freq):
                res.append(-num)
        
        return res

---

History

Jan-24-2026 Solved

• heap not familiar

Jan-17-2026 Solved, use both method