1636. Sort Array by Increasing Frequency

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.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

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

Constraints:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

Approach 01

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        vector<int> result;
        vector<pair<int, int>> s;
        
        for(int i=0; i<n; i++){
            ++mp[nums[i]];
        }

        for(auto &i: mp){
            s.push_back({i.second, i.first});
        }

        auto lambda = [](auto a, auto b){
            if(a.first != b.first){
                return a.first > b.first;
            }
            else{
                return a.second < b.second;
            }
        };

        sort(s.rbegin(), s.rend(), lambda);

        for(auto &i: s){
            for(int j=0; j < i.first; j++){
                result.push_back(i.second);
            }
        }
        return result;
    }
};

from typing import List
from collections import defaultdict

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count_map = defaultdict(int)
        result = []
        count_pairs = []
        
        for i in range(n):
            count_map[nums[i]] += 1

        for num, freq in count_map.items():
            count_pairs.append((freq, num))

        def compare(a, b):
            if a[0] != b[0]:
                return a[0] - b[0]
            else:
                return b[1] - a[1]

        count_pairs.sort(key=lambda x: (x[0], -x[1]))

        for freq, num in count_pairs:
            for _ in range(freq):
                result.append(num)

        return result

Time Complexity

• Counting Frequencies:

  Iterating through the array nums to count the frequencies of each number takes \( O(n) \) time, where \( n \) is the number of elements in nums.

• Building the Frequency Pairs Vector:

  Creating the vector s of pairs from the frequency map takes \( O(m) \) time, where \( m \) is the number of unique elements in nums.

• Sorting:

  Sorting the vector s takes \( O(m \log m) \) time, where \( m \) is the number of unique elements. The sorting function includes a custom comparator, but it does not change the overall complexity.

• Building the Result Vector:

  Iterating through the sorted vector s and constructing the result vector result takes \( O(n) \) time, as we are placing all elements back into the result vector.

• Overall Time Complexity:

  The overall time complexity is \( O(n + m \log m) \), where \( n \) is the number of elements in nums and \( m \) is the number of unique elements in nums.

Space Complexity

• Auxiliary Space:

  The unordered map mp for storing frequencies takes \( O(m) \) space, where \( m \) is the number of unique elements.

• Additional Vectors:

  The vectors s and result take \( O(m) \) and \( O(n) \) space respectively, where \( m \) is the number of unique elements and \( n \) is the number of elements in nums.

• Overall Space Complexity:

  The overall space complexity is \( O(n + m) \), where \( n \) is the number of elements in nums and \( m \) is the number of unique elements in nums.

Approach 02

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> count;
        vector<pair<int, int>> frequency_pairs;
        
        // Count the frequency of each number
        for (int num : nums) {
            count[num]++;
        }

        // Create a list of pairs (frequency, number)
        for (auto& it : count) {
            frequency_pairs.push_back({it.second, it.first});
        }

        // Sort by frequency in ascending order, then by value in descending order
        sort(frequency_pairs.begin(), frequency_pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first == b.first)
                return a.second > b.second; // Sort by value in descending order
            return a.first < b.first; // Sort by frequency in ascending order
        });

        vector<int> result;
        for (auto& p : frequency_pairs) {
            result.insert(result.end(), p.first, p.second);
        }

        return result;
    }
};

from collections import Counter
from typing import List

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        # Create a list of tuples (frequency, number)
        frequency_pairs = [(freq, num) for num, freq in count.items()]
        
        # Sort by frequency in ascending order, then by value in descending order
        frequency_pairs.sort(key=lambda x: (x[0], -x[1]))
        
        result = []
        for freq, num in frequency_pairs:
            result.extend([num] * freq)
        
        return result

Time Complexity

• Counting Frequencies:

  Iterating through the array nums to count the frequencies of each number takes \( O(n) \) time, where \( n \) is the number of elements in nums.

• Building the Frequency Pairs Vector:

  Creating the vector frequency_pairs of pairs from the frequency map takes \( O(m) \) time, where \( m \) is the number of unique elements in nums.

• Sorting:

  Sorting the vector frequency_pairs takes \( O(m \log m) \) time, where \( m \) is the number of unique elements. The sorting function includes a custom comparator, but it does not change the overall complexity.

• Building the Result Vector:

  Iterating through the sorted vector frequency_pairs and constructing the result vector result takes \( O(n) \) time, as we are placing all elements back into the result vector.

• Overall Time Complexity:

  The overall time complexity is \( O(n + m \log m) \), where \( n \) is the number of elements in nums and \( m \) is the number of unique elements in nums.

Space Complexity

• Auxiliary Space:

  The unordered map count for storing frequencies takes \( O(m) \) space, where \( m \) is the number of unique elements.

• Additional Vectors:

  The vector frequency_pairs takes \( O(m) \) space and the vector result takes \( O(n) \) space, where \( m \) is the number of unique elements and \( n \) is the number of elements in nums.

• Overall Space Complexity:

  The overall space complexity is \( O(n + m) \), where \( n \) is the number of elements in nums and \( m \) is the number of unique elements in nums.