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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Array by Increasing Frequency

Difficulty: Easy

Problem Description

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order. Return the sorted array.

Key Insights

  • The frequency of each element must be calculated.
  • Sorting must be done based on frequency first and, in case of a tie, based on the value itself in decreasing order.
  • A hash table (or dictionary) can be used to track the frequency of each element efficiently.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of elements in the array due to the sorting step.
Space Complexity: O(n), for storing the frequency counts in a hash table.

Solution

To solve this problem, we can follow these steps:

  1. Use a hash table (dictionary) to count the frequency of each element in the array.
  2. Convert the hash table into a list of tuples where each tuple contains the element and its frequency.
  3. Sort this list of tuples first by frequency (ascending) and then by the element value (descending).
  4. Construct the final sorted array based on the sorted tuples.

This approach ensures that we adhere to the problem's requirements for sorting based on frequency and value.

Code Solutions

from collections import defaultdict

def frequencySort(nums):
    # Step 1: Count the frequency of each element
    frequency = defaultdict(int)
    for num in nums:
        frequency[num] += 1
    
    # Step 2: Create a list of tuples (num, frequency)
    freq_list = [(num, freq) for num, freq in frequency.items()]
    
    # Step 3: Sort the list by frequency and then by value
    freq_list.sort(key=lambda x: (x[1], -x[0]))
    
    # Step 4: Construct the sorted array
    sorted_array = []
    for num, freq in freq_list:
        sorted_array.extend([num] * freq)
    
    return sorted_array
← Back to All Questions