We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Array by Increasing Frequency

Number: 1741

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Bloomberg, Accenture, Agoda, Apple, Oracle, Goldman Sachs

Problem Description

Given an array of integers, sort the array such that the integers with a lower frequency appear first. For numbers with the same frequency, sort them in decreasing order. Return the sorted array.

Key Insights

  • Count the frequency of each integer using a hash table or dictionary.
  • Sort the array using a custom comparator:
    • Primary key: frequency in ascending order.
    • Secondary key: the integer value in descending order when frequencies are equal.
  • Use built-in sort functions with custom key functions to achieve the desired order.

Space and Time Complexity

Time Complexity: O(n log n), where n is the length of the array (sorting dominates the complexity). Space Complexity: O(n) for storing frequency counts.

Solution

The solution involves two main steps. First, traverse the array and count the frequency of each element using a hash table (or dictionary). Next, sort the array by using a custom key where each element is mapped to a tuple consisting of its frequency (for increasing order) and its negative value (for decreasing order when frequencies are equal). This transforms the problem into a standard sorting problem with a custom comparator.

Code Solutions

# Python solution
def frequencySort(nums):
    # Step 1: Count the frequency of each element in the array
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Step 2: Sort the array using a custom key
    # The key returns a tuple (frequency, negative of num)
    # so that lower frequency comes first and in case of tie,
    # higher number comes first (because of negative sorting).
    nums.sort(key=lambda x: (frequency[x], -x))
    return nums

# Example usage
if __name__ == "__main__":
    input_nums = [1, 1, 2, 2, 2, 3]
    print(frequencySort(input_nums))  # Output: [3, 1, 1, 2, 2, 2]
← Back to All Questions