Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2

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

Solution

Method 1 - Using Frequency map and then sort

We can follow these steps:

  1. Use a frequency count to determine how often each integer occurs in the array.
  2. Sort the array based on the frequency count in increasing order.
  3. For integers that have the same frequency, sort them in decreasing order.

Here is the video explanation of the same:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {

	public int[] frequencySort(int[] nums) {
		// Step 1: Count frequencies
		Map<Integer, Integer> map = new HashMap<>();

		for (int num: nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		// Step 2: Convert array to list for easier sorting
		List<Integer> numList = new ArrayList<>();

		for (int num: nums) {
			numList.add(num);
		}

		// Step 3: Sort using custom comparator
		numList.sort((a, b) -> map.get(a) == map.get(b) ? b - a: map.get(a).compareTo(map.get(b)));


		// Step 4: Convert list back to array
		for (int i = 0; i < nums.length; i++) {
			nums[i] = numList.get(i);
		}

		return nums;
	}

}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public class Solution {

public int[] frequencySort(int[] nums) {
	Map<Integer, Integer> map = new HashMap<>();
	// count frequency of each number
	Arrays.stream(nums).forEach(n -> map.put(n, map.getOrDefault(n, 0) + 1));
	// custom sort
	return Arrays.stream(nums).boxed()
			.sorted((a,b) -> map.get(a) != map.get(b) ? map.get(a) - map.get(b) : b - a)
			.mapToInt(n -> n)
			.toArray();
}

}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from collections import Counter


def frequency_sort(nums):
    # Step 1: Count the frequency of each element
    freq = Counter(nums)

    # Step 2: Sort based on frequency, and by value in decreasing order for ties in frequency
    nums.sort(key=lambda x: (freq[x], -x))

    return nums

Complexity

  • ⏰ Time complexity: O(n log n), where n is number of elements
    • Add values to frequency map takes O(n) time
    • Sorting the list takes O(n log n) time
  • 🧺 Space complexity: O(n)
    • For using frequency map, and using list in java solution