Sort elements of an array based on frequency

Given an array of integers, sort the elements based on their frequency in descending order. If two elements have the same frequency, the element with the higher value should appear first. Return the array sorted by these criteria.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [4, 5, 6, 5, 4, 3]
Output: [4, 4, 5, 5, 6, 3]
Explanation: Elements 4 and 5 both appear twice, and they are sorted in descending order. Element 6 appears once and is greater than 3.

Example 2:
Input:
arr = [1, 2, 3, 2, 4, 1]
Output: [1, 1, 2, 2, 3, 4]
Explanation: Elements 1 and 2 both appear twice, and 1 and 2 are placed before 3 and 4, which appear once each.

Example 3:
Input:
arr = [2, 3, 2, 4, 4, 4, 1, 5]
Output: [4, 4, 4, 2, 2, 3, 5, 1]
Explanation: Element 4 appears thrice, followed by 2 which appears twice. Elements 3, 5, and 1 appear once each and are ordered by value.

Approach to sort the elements of an array based on their frequency

  1. Count Frequencies:
    • Use a hash map or dictionary to count the frequency of each element in the array.
  2. Sort by Frequency and Value:
    • Convert the elements and their frequencies into a list of tuples.
    • Sort the list by frequency in descending order. If two elements have the same frequency, sort them by the element’s value in descending order.
  3. Build the Result:
    • Reconstruct the array based on the sorted list, repeating each element according to its frequency.

C++ Program to sort the elements of an array based on their frequency

cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Comparator function to sort by frequency and then by value
bool compare(pair<int, int>& a, pair<int, int>& b) {
    if (a.second == b.second)
        return a.first > b.first; // Sort by value in descending order
    return a.second > b.second;   // Sort by frequency in descending order
}

// Function to sort array by frequency
vector<int> sortByFrequency(vector<int>& arr) {
    unordered_map<int, int> freqMap;

    // Count the frequency of each element
    for (int num : arr) {
        freqMap[num]++;
    }

    // Create a vector of pairs (element, frequency)
    vector<pair<int, int>> freqList(freqMap.begin(), freqMap.end());

    // Sort the frequency list by frequency and then by value
    sort(freqList.begin(), freqList.end(), compare);

    // Build the result array
    vector<int> result;
    for (auto& elem : freqList) {
        result.insert(result.end(), elem.second, elem.first);
    }

    return result;
}

int main() {
    vector<int> arr = {4, 5, 6, 5, 4, 3};
    vector<int> result = sortByFrequency(arr);

    cout << "Array sorted by frequency: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Program to sort the elements of an array based on their frequency

java
import java.util.*;

public class SortByFrequency {

    // Function to sort array by frequency
    public static List<Integer> sortByFrequency(int[] arr) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        // Count the frequency of each element
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Create a list from elements of the frequency map
        List<Map.Entry<Integer, Integer>> freqList = new ArrayList<>(freqMap.entrySet());

        // Sort the frequency list by frequency and then by value
        freqList.sort((a, b) -> {
            if (a.getValue().equals(b.getValue())) {
                return b.getKey() - a.getKey(); // Sort by value in descending order
            }
            return b.getValue() - a.getValue(); // Sort by frequency in descending order
        });

        // Build the result list
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> elem : freqList) {
            for (int i = 0; i < elem.getValue(); i++) {
                result.add(elem.getKey());
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 5, 4, 3};
        List<Integer> result = sortByFrequency(arr);

        System.out.println("Array sorted by frequency: " + result);
    }
}

Python Program to sort the elements of an array based on their frequency

python
from collections import Counter

# Function to sort array by frequency
def sort_by_frequency(arr):
    # Count the frequency of each element
    freq_map = Counter(arr)

    # Sort the elements first by frequency and then by value
    sorted_elements = sorted(freq_map.items(), key=lambda x: (-x[1], -x[0]))

    # Build the result list
    result = []
    for value, frequency in sorted_elements:
        result.extend([value] * frequency)

    return result

# Example usage
if __name__ == "__main__":
    arr = [4, 5, 6, 5, 4, 3]
    result = sort_by_frequency(arr)
    print("Array sorted by frequency:", result)

Time Complexity

  • O(n log n): Counting frequencies takes O(n), while sorting based on frequency and value takes O(n log n).

Space Complexity

  • O(n): The algorithm uses additional space for storing frequencies and the sorted list.

DSA

4140

668

Related Articles