Sort Array by Increasing Frequency - Practice Coding Problems

Sort Array by Increasing Frequency - 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.

Input & Output

Example 1 — Basic Case

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

› Output: [3,1,1,2,2,2]

💡 Note: Frequencies: 1 appears 2 times, 2 appears 3 times, 3 appears 1 time. Sort by frequency: 3(1 time), 1(2 times), 2(3 times)

Example 2 — Same Frequencies

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

› Output: [1,3,3,2,2]

💡 Note: Frequencies: 1→1, 2→2, 3→2. Same frequency elements (2,3) sorted by value descending: 3 before 2

Example 3 — All Different

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

› Output: [5,-1,4,4,-6,-6,1,1,1]

💡 Note: Frequencies: 5→1, -1→1, 4→2, -6→2, 1→3. Sort by frequency ascending, same frequency by value descending

Constraints

1 ≤ nums.length ≤ 100
-100 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each element in the array

Sort Rules

Primary: frequency ascending, Secondary: value descending for ties

Output

Array sorted by the two-level criteria

Key Takeaway

🎯 Key Insight: Use two-level sorting - frequency first (ascending), then value (descending) for equal frequencies

Asked in

a Amazon 3 🍎 Apple 2

The key insight is to use a two-level sorting criteria: primary by frequency ascending, secondary by value descending. Best approach uses hash map for O(n) frequency counting + O(n log n) sorting. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Count frequency of each element manually, then sort using nested loops
Frequency Count + Sort	O(n log n)	O(n)	Use hash map to count frequencies, then sort with custom comparator

Brute Force — Algorithm Steps

Step 1: For each element, count frequency by scanning array
Step 2: Sort using nested loops with custom comparison

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

For each element, scan entire array to count occurrences

Compare & Swap

Use nested loops to compare and swap elements based on frequency rules

Result

Array sorted by frequency ascending, value descending for ties

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countFrequency(int* nums, int size, int target) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] == target) count++;
    }
    return count;
}

int* solution(int* nums, int size) {
    // Bubble sort with custom comparison
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int freqI = countFrequency(nums, size, nums[i]);
            int freqJ = countFrequency(nums, size, nums[j]);
            
            int shouldSwap = 0;
            if (freqI > freqJ) {
                shouldSwap = 1;
            } else if (freqI == freqJ && nums[i] < nums[j]) {
                shouldSwap = 1;
            }
            
            if (shouldSwap) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }
    
    return nums;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    solution(nums, size);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        if (i > 0) printf(",");
        printf("%d", nums[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) for counting frequencies + O(n²) for bubble sort

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables, sorting in-place

✓ Linear Space

120.0K Views

Medium Frequency

~15 min Avg. Time

2.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler