algoadvance

Leetcode 1636. Sort Array by Increasing Frequency

Problem Statement

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.

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 based on the 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

Clarifying Questions

1. Should negative numbers be handled any differently?
   • No, treat negative numbers the same as positive ones.
2. Should we modify the input array directly or return a new array?
   • We should return the new array that is sorted based on the above conditions.

Strategy

To solve this problem, we can:

1. Count the frequency of each element in the array.
2. Use a custom comparison to sort the elements:
   • Primary key: Frequency (in increasing order).
   • Secondary key: Value (in decreasing order if frequencies are the same).

Code

Here’s the C++ implementation:

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        // Step 1: Count frequencies
        unordered_map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
        }
        
        // Step 2: Sort with custom comparator
        sort(nums.begin(), nums.end(), [&frequencyMap](int a, int b) {
            if (frequencyMap[a] == frequencyMap[b])
                return a > b;
            return frequencyMap[a] < frequencyMap[b];
        });
        
        return nums;
    }
};

Explanation

• Step 1: We first count the occurrences/frequencies of each number using an unordered_map.
• Step 2: We then sort the array using std::sort with a lambda function as the custom comparator.
  • The lambda compares based on frequency first.
  • If frequencies are the same, it uses the actual value in descending order.

Time Complexity

• Counting frequencies takes O(N), where N is the number of elements in the array.
• Sorting takes O(N log N) due to the complexity of std::sort.
• Overall, the time complexity is O(N log N).

This solution is efficient given the constraints, and the use of unordered_map ensures that the frequency counting is optimal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?