LeetCode 1636 - Sort Array by Increasing Frequency

LeetCode Problem 1636

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to reorder an array of integers based on the frequency of each value. Specifically, elements with lower frequency should appear before elements with higher frequency. If two elements have the same frequency, the one with the larger value should appear first. In other words, the sort is primary by increasing frequency and secondary by decreasing numeric value.

The input is an array nums containing integers in the range [-100, 100] with a length between 1 and 100. The output is a new array containing the same elements but sorted according to the rules above.

Important edge cases include arrays with all elements the same (frequency tie for all elements), arrays where negative numbers are present, arrays with a single element, and arrays with multiple elements having the same frequency. The constraints are small, so even straightforward sorting solutions are feasible.

Approaches

The brute-force approach would involve counting the frequency of each element manually, creating multiple arrays for each frequency, and then concatenating them in the correct order. This works but involves extra bookkeeping and unnecessary complexity.

The key insight for an optimal solution is to use a hash map to count the frequency of each element and then use a custom sort on the original array. Sorting can directly apply the rules: sort by frequency ascending and by value descending for tie-breaking. This is simple, efficient, and leverages built-in sort functionality for clarity and correctness.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Count frequency manually, group by frequency, then sort groups
Optimal	O(n log n)	O(n)	Use hash map for frequency counting, then sort array with custom comparator

Algorithm Walkthrough

1. Initialize a hash map freq to store the frequency of each number in nums. Loop through nums and increment the count for each number. This allows us to know how many times each number occurs.
2. Sort nums using a custom key. The key is a tuple (frequency, -value), where frequency is obtained from freq. The negative sign ensures that larger numbers come first when frequencies are equal.
3. Return the sorted array.

Why it works: Each element is compared based on its frequency first and its value second. Python and Go sorts are stable, meaning elements with equal keys preserve relative order, which ensures tie-breaking works correctly. This guarantees that the output respects both sorting conditions.

Python Solution

from typing import List
from collections import Counter

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

The Python implementation uses Counter to count frequencies efficiently. The sorted function accepts a key function, which provides a tuple (frequency, -value) for each element. This handles both the primary and secondary sorting conditions in one step. The result is returned as a new sorted list.

Go Solution

import "sort"

func frequencySort(nums []int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }
    sort.Slice(nums, func(i, j int) bool {
        if freq[nums[i]] == freq[nums[j]] {
            return nums[i] > nums[j]
        }
        return freq[nums[i]] < freq[nums[j]]
    })
    return nums
}

In Go, we use a map to count frequencies and sort.Slice to sort the slice in-place. The comparator function first checks the frequency; if frequencies are equal, it returns the element with the larger value first. The solution handles empty slices naturally because the for loop and sort.Slice safely operate on empty inputs.

Worked Examples

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

Step	freq	Sort Key	Sorted Array
Count	{1:2, 2:3, 3:1}	[(2,-1),(2,-1),(3,-2),(3,-2),(3,-2),(1,-3)]	[3,1,1,2,2,2]

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

Step	freq	Sort Key	Sorted Array
Count	{2:2, 3:2, 1:1}	[(2,-2),(2,-3),(1,-1),(2,-3),(2,-2)]	[1,3,3,2,2]

Example 3: nums = [-1,1,-6,4,5,-6,1,4,1]

Step	freq	Sort Key	Sorted Array
Count	{-6:2,-1:1,1:3,4:2,5:1}	[(1,1),(3,-1),(2,-6),(2,-4),(1,-5),(2,-6),(3,-1),(2,-4),(3,-1)]	[5,-1,4,4,-6,-6,1,1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; frequency counting is O(n)
Space	O(n)	Hash map stores up to n entries

The complexity reasoning relies on the fact that the frequency counting is linear and sorting is the standard n log n operation. Space is dominated by the hash map for frequency counts.

Test Cases

# Provided examples
assert Solution().frequencySort([1,1,2,2,2,3]) == [3,1,1,2,2,2]
assert Solution().frequencySort([2,3,1,3,2]) == [1,3,3,2,2]
assert Solution().frequencySort([-1,1,-6,4,5,-6,1,4,1]) == [5,-1,4,4,-6,-6,1,1,1]

# Edge cases
assert Solution().frequencySort([1]) == [1]  # single element
assert Solution().frequencySort([2,2,2,2]) == [2,2,2,2]  # all elements identical
assert Solution().frequencySort([-1,-2,-3,-1,-2,-3]) == [-1,-1,-2,-2,-3,-3]  # negative numbers
assert Solution().frequencySort([3,3,1,1,2,2,4]) == [4,3,3,2,2,1,1]  # tie frequencies

Test	Why
[1,1,2,2,2,3]	Tests basic frequency-based sorting
[2,3,1,3,2]	Tests tie-breaking by value
[-1,1,-6,4,5,-6,1,4,1]	Tests combination of positive and negative numbers
[1]	Single-element edge case
[2,2,2,2]	All elements same, no sorting needed
[-1,-2,-3,-1,-2,-3]	Negative numbers and tie frequencies
[3,3,1,1,2,2,4]	Multiple tie frequencies with unique element

Edge Cases

One edge case is a single-element array. Since there is only one element, the frequency and tie-breaking logic do not change the array, and the function must return it correctly.

A second edge case is when all elements are the same. The frequency sort will detect equal frequencies, but since all values are identical, the tie-breaking logic does not affect the output. This ensures the function handles homogeneous arrays gracefully.

A third edge case involves negative numbers and frequency ties. Negative numbers reverse the order in the tie-breaking logic when using -x in Python or nums[i] > nums[j] in Go. The implementation correctly sorts larger negative numbers (closer to zero) before smaller negative numbers when frequencies are equal.