algoadvance

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

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

1. Q: What should we do if the input list is empty?
   • A: Return an empty list.
2. Q: Are there any constraints on the size of the input list?
   • A: The problem does not explicitly state constraints, but typical LeetCode constraints apply.
3. Q: Can the input list contain duplicates?
   • A: Yes, as indicated by the examples.

Strategy

1. Frequency Calculation:
   • Use a dictionary or Counter from the collections module to count the frequency of each element in nums.
2. Sort with Custom Logic:
   • Sort the array with a custom key:
     • The primary key is the frequency of the elements (ascending).
     • The secondary key is the value of the elements (descending).
3. Reconstruct Result:
   • Construct the result based on the sorted elements.

Code

from collections import Counter

def frequencySort(nums):
    # Step 1: Count the frequency of each number
    freq = Counter(nums)
    
    # Step 2: Sort based on custom logic
    nums.sort(key=lambda x: (freq[x], -x))
    
    return nums

# Example Usage
print(frequencySort([1,1,2,2,2,3]))  # Output: [3,1,1,2,2,2]
print(frequencySort([2,3,1,3,2]))    # Output: [1,3,3,2,2]
print(frequencySort([-1,1,-6,4,5,-6,1,4,1]))  # Output: [5,-1,4,4,-6,-6,1,1,1]

Time Complexity

• Frequency Counting: O(N) where N is the number of elements in nums, as we iterate through the list once to count frequencies.
• Sorting: O(N log N) due to the sorting step. The custom sorting function operates in constant time O(1) for each comparison.
• Overall Complexity: O(N log N) due to the sorting being the dominant step.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?