Sort Array by Increasing Frequency Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Bloomberg C3 IoT eBay Facebook Google Oracle Twilio
Array HashMap SortingsViews 2423

Problem Statement

The Sort Array by Increasing Frequency LeetCode Solution – “Sort Array by Increasing Frequency” states that you’re given an array of integers, sort the array in increasing order based on the frequency of the values. Two or more values have the same frequency, we need to sort them in decreasing order.

Example:

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

Explanation:

  • The frequency of 1 is 2, the frequency of 2 is 3, and the frequency of 3 is 1.
  • Since element 3 has the minimum frequency, hence the occurrences of 3 will come first.
  • Element 1 has the second minimum frequency hence, occurrences of element 1 will come after occurrences of element 3.
  • Hence, occurrences of element 2 come at the end.
  • The Final Sorted Array is: [3,1,1,2,2,2].
Input:  nums = [2,3,1,3,2]
Output: [1,3,3,2,2]

Explanation:

  • The frequency of 1 is 1, the frequency of 2 is 2, and the frequency of 3 is 2.
  • Since element 1 has the minimum frequency, hence the occurrences of 1 will come first.
  • Element 2 and Element 3 have the same frequency, all the occurrences of 3 will come before all the occurrences of 2.
  • Occurrences of element 2 will come at the end of the array.
  • The Final Sorted Array is: [1,3,3,2,2].

Approach

Idea:

  1. The main idea to solve this problem is to use Sortings.
  2. First, store all the frequencies of the unique elements in the Hashmap which takes O(N) constant space and O(1) time if we use an efficient hash function.
  3. Sort the input array using the lambda function which compares:
    1. if the frequency of the first number is strictly less than the frequency of the second number, return true.
    2. if the frequency of both the numbers is equal, compare the two numbers.
  4. Return the sorted array.

Code

Sort Array By Increasing Frequency Leetcode C++ Solution:

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int,int> freq;
        for(auto& num:nums){
            freq[num]++;
        }
        sort(nums.begin(),nums.end(),[&](const int a,const int b){
            if(freq[a]==freq[b]){
                return a>b;
            }
            return freq[a]<freq[b];
        });
        return nums;
    }
};

Sort Array By Increasing Frequency Leetcode Java Solution:

class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Arrays.stream(nums).forEach(n -> freq.put(n, freq.getOrDefault(n, 0) + 1));
        return Arrays.stream(nums).boxed().sorted((a,b) -> freq.get(a) != freq.get(b) ? freq.get(a) - freq.get(b) : b - a).mapToInt(n -> n).toArray();
    }
}

Complexity Analysis for Sort Array by Increasing Frequency Leetcode Solution

Time Complexity

The time complexity of the above code is O(NlogN).

Space Complexity

The space complexity of the above code is O(N). Storing the frequencies of each unique element in the hashmap takes O(N) Space.

Translate »