💬 Discord
Sign In
NeetCode #96LC-1636EasyArrays & Hashing
← Back to All Problems

#96 · #1636 · Sort Array by Increasing Frequency(按照频率将数组升序排序)

📌 Problem Statement & Constraints

Given an integer array nums, sort it in ascending order of frequency, breaking ties in descending order of value. Constraints: 1 <= nums.length <= 100, -100 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. Count the frequencies, then sort with a composite key.
  2. The key is (frequency ascending, value descending), which in Python is key=lambda x: (cnt[x], -x).
  3. Sorting the original array with that key keeps every duplicate adjacent and in the required order.
  4. Because -100 <= nums[i] <= 100, a counting array indexed by value plus 100 is a valid O(n + V) alternative.

💻 Benchmark Python3 Implementation

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        from collections import Counter
        cnt = Counter(nums)
        return sorted(nums, key=lambda x: (cnt[x], -x))   # freq asc, value desc

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates. A counting-array bucket approach would be O(n + V) with V = 201.
💾 Space Complexity
O(n) for the sorted copy plus O(k) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the tie-break on value: the problem explicitly requires descending value order for equal frequencies.
  • Using key=lambda x: (cnt[x], x): this gives ascending value on ties, the opposite of the requirement.
  • Sorting the counter's items and expanding: workable, but sorting the original array is simpler and automatically emits the right number of copies.