#1636

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sort Array by Increasing Frequency

Sort Array by Increasing Frequency requires counting each element and ordering them by frequency, breaking ties with descending values for accuracy.

array hash table sorting

Problem Statement

Given an integer array nums, return a new array where the integers are sorted in ascending order by their frequency. If multiple numbers share the same frequency, place the larger numbers first.

For example, given nums = [1,1,2,2,2,3], the sorted output is [3,1,1,2,2,2] because '3' occurs once, '1' occurs twice, and '2' occurs three times. The array length ranges from 1 to 100, and values may be negative or positive.

Examples

Example 1

Input: nums = [1,1,2,2,2,3]

Output: [3,1,1,2,2,2]

'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]

'2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3

Input: nums = [-1,1,-6,4,5,-6,1,4,1]

Output: [5,-1,4,4,-6,-6,1,1,1]

Example details omitted.

Constraints

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution Approach

Count Frequencies Using a Hash Map

Scan the input array and populate a hash map where keys are numbers and values are their counts. This ensures direct access to frequencies, enabling O(1) lookups during sorting.

Sort by Frequency and Value

Use a custom sort on the array where elements are first compared by frequency in ascending order, then by value in descending order to correctly handle ties.

Return the Sorted Array

After sorting, return the array as the result. This two-step separation between counting and sorting prevents errors from mismanaging tie-breaking rules.

Complexity Analysis

Metric	Value
Time	O(N \cdot logN)
Space	O(N)

Time complexity is O(N log N) due to sorting the array, and space complexity is O(N) for storing frequency counts in a hash map.

What Interviewers Usually Probe

Look for clear separation between counting and sorting steps.
Watch for proper tie-breaking by descending value when frequencies match.
Ensure the solution scales within the 100-element constraint efficiently.

Common Pitfalls or Variants

Common pitfalls

Sorting only by frequency and ignoring descending value tie-breaking.
Using nested loops instead of a hash map for frequency counting.
Mutating the input array unnecessarily, causing side effects.

Follow-up variants

Sort array by decreasing frequency with ascending value ties.
Return only the top k frequent elements in sorted order.
Handle very large arrays where counts exceed integer limits.

FAQ

What is the main pattern in Sort Array by Increasing Frequency?

The primary pattern is array scanning combined with hash lookup to count occurrences and then sorting by frequency with tie-breaking.

Can negative numbers be in the input array?

Yes, nums[i] can be negative, and the solution must handle their frequencies just like positive numbers.

Is it necessary to modify the original array?

No, it's safer to return a new array after sorting to avoid side effects and maintain clarity.

What is the expected time complexity?

O(N log N), mainly due to sorting, with O(N) space for frequency counting in a hash map.

How does tie-breaking work for equal frequencies?

Elements with the same frequency are placed in descending order, ensuring larger values appear first in ties.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

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

Continue Practicing

#1630 arithmetic subarrays #1604 alert using same key card three or more times in a one hour period #1679 max number of k sum pairs