Domain 1EasyCORE

Sort Array by Increasing Frequency

The problem requires sorting an array of integers based on the frequency of their occurrences in increasing order. If two numbers have the same frequency, they should be sorted in decreasing order. The input is an array of integers `nums`, and the output is a sorted array according to the specified rules.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Sort

1636. Sort Array by Increasing Frequency

Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 66.7%


Problem Breakdown

The problem requires sorting an array of integers based on the frequency of their occurrences in increasing order. If two numbers have the same frequency, they should be sorted in decreasing order. The input is an array of integers nums, and the output is a sorted array according to the specified rules.

Inputs:

  • An array of integers nums where each integer is between -100 and 100.
  • The length of the array is between 1 and 100.

Outputs:

  • A sorted array of integers based on frequency and value order.

Implicit Constraints/Edge Cases:

  • If the input array has only one element, it should be returned as is.
  • If all elements have the same frequency, they should be sorted in decreasing order.
  • The array can contain negative numbers, zeros, and positive numbers.

Intuition

The brute-force approach would involve counting the frequency of each number using a dictionary or hashmap, then sorting the array based on these frequencies. However, this approach might not be efficient enough for larger arrays due to its time complexity.

A better approach involves using Python’s built-in sorting capabilities with a custom key function. This allows us to sort the array in one pass by leveraging the fact that tuples are compared lexicographically (i.e., first by frequency and then by value).

Approach

  1. Count Frequencies: Use a dictionary to count the frequency of each number in the input array.
  2. Sort with Custom Key: Sort the array using Python’s sorted() function with a custom key that sorts primarily by frequency in increasing order and secondarily by value in decreasing order.

Algorithm Steps:

  1. Initialize an empty dictionary freq to store the frequency of each number.
  2. Iterate through the input array nums and populate the freq dictionary.
  3. Use the sorted() function with a custom key that sorts the numbers first by their frequency (in increasing order) and then by their value (in decreasing order).
  4. Return the sorted array.

Complexity Analysis

  • Time Complexity: O(n log n), where n is the length of the input array. This is due to the sorting step.
  • Space Complexity: O(n), for storing the frequency dictionary.

Solution

def frequencySort(nums):
    # Step 1: Count frequencies
    freq = {}
    for num in nums:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    
    # Step 2: Sort with custom key
    sorted_nums = sorted(nums, key=lambda x: (freq[x], -x))
    
    return sorted_nums

Edge Cases Handled

  • Single Element Array: The function will correctly return the single element as is.
  • All Elements with Same Frequency: The function will sort these elements in decreasing order.
  • Negative Numbers, Zeros, and Positive Numbers: The function handles all types of integers correctly.