#1636 Sort Array by Increasing Frequency

frequently reported atAdobe Amazon

the problem

In plain words

Sort nums by how often each value appears (rarer first). If two values appear equally often, put the larger value first.

in nums = [1,1,2,2,2,3]

out [3,1,1,2,2,2]

in nums = [2,3,1,3,2]

out [1,3,3,2,2]

2 and 3 both appear twice → 3 first.

in nums = [-1,1,-6,4,5,-6,1,4,1]

out [5,-1,4,4,-6,-6,1,1,1]

1 ≤ n ≤ 100
-100 ≤ nums[i] ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSort with a custom comparator Frequency counting

Count first, then sort with a two-key comparator: frequency ascending, then value descending. This is the textbook comparing(...).thenComparing(...) problem.

solutions

From brute force to optimal

Count each element's frequency with a full scan, then sort boxed values.

For each element, scan the array to count it.
Sort Integer[] by (freq asc, value desc).

timeO(n²)

n scans of length n (the sort is O(n log n)).

spaceO(n)

Boxed copy and the frequency map.

javajava.util.*

1class Solution {2    public int[] frequencySort(int[] nums) {3        int n = nums.length;4        Integer[] boxed = new Integer[n];5        Map<Integer, Integer> freq = new HashMap<>();6        for (int i = 0; i < n; i++) {7            boxed[i] = nums[i];8            int c = 0;9            for (int x : nums) if (x == nums[i]) c++;   // O(n) scan per element10            freq.put(nums[i], c);11        }12        Arrays.sort(boxed, (a, b) -> !freq.get(a).equals(freq.get(b))13                ? Integer.compare(freq.get(a), freq.get(b))   // rarer first14                : Integer.compare(b, a));                     // tie → bigger value first15        for (int i = 0; i < n; i++) nums[i] = boxed[i];16        return nums;17    }18}

Count once into an array of 201 slots, then sort with comparingInt(freq).thenComparing(reverseOrder()).

freq[x + 100]++.
Box to Integer[].
Sort by frequency, ties by value descending.
Unbox.

timeO(n log n)

One counting pass plus the sort.

spaceO(n)

Boxed array (the count array is a constant 201).

javajava.util.*

1class Solution {2    public int[] frequencySort(int[] nums) {3        int[] freq = new int[201];                     // values are in [-100, 100]4        for (int x : nums) freq[x + 100]++;5        Integer[] boxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);6        Arrays.sort(boxed, Comparator7                .comparingInt((Integer x) -> freq[x + 100])          // frequency ascending8                .thenComparing(Comparator.reverseOrder()));         // value descending9        for (int i = 0; i < nums.length; i++) nums[i] = boxed[i];10        return nums;11    }12}

No comparator: for f = 1, 2, …, write every value with frequency f, biggest value first.

Count.
For f = 1.. while output not full: for v = 100 down to −100, if freq[v] == f write v f times.

timeO(n + R·F)

R = 201 values checked for each frequency level up to the max frequency F ≤ n.

spaceO(R)

Only the count array; output overwrites nums.

javajava.util.*

1class Solution {2    public int[] frequencySort(int[] nums) {3        int[] freq = new int[201];4        for (int x : nums) freq[x + 100]++;5        int k = 0;6        for (int f = 1; f <= nums.length && k < nums.length; f++) {  // rarest group first7            for (int v = 100; v >= -100; v--) {                       // inside a group: biggest value first8                if (freq[v + 100] == f) {9                    for (int c = 0; c < f; c++) nums[k++] = v;10                }11            }12        }13        return nums;14    }15}

in the room

How to say it in the interview

talk track

State both sort keys explicitly before coding — the tie-break (value descending) is where people slip.

traps

int[] can't take a comparator — box to Integer[] or use a list.
Getting the tie-break direction wrong.

what they ask next

Follow-ups

Sort Characters By Frequency (LC 451)?

Same counting, then bucket by frequency (most frequent first) — O(n).

before you submit

Edge cases to test

All values distinct: every frequency is 1, so the answer is plain descending order.
Negative values: shift by +100 before indexing the count array.
One value repeated: nothing moves.

practise next