# Sort Elements of an Array by Frequency

Sort Elements of an Array by Frequency

Problem Statement: Given an array of integers, having some duplicate elements, sort the array by frequency.

Examples:

```Example 1:
Input: N = 8, array[] = {1,2,3,2,4,3,1,2}
Output: 2 2 2 1 1 3 3 4
Explanation: Since  2 is present 3 times in an array , so print it 3 times ,then print ‘1’ 2 times and then ‘3’ 2 times and 4 has least frequency, it will be printed at last.

Example 2:
Input: N = 6, array[] = {-199,6,7,-199,3,5}
Output: -199 -199 3 5 6 7
Explanation: Since -199 is present 2 times so it will be printed at first , then 3 , 5 ,6 ,7 are present once in array , so print them in their sorted order.
```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

ApproachBrute Force

Step 1: Sort the given array.

Step 2: Now create a 2d array having the first row for storing distinct elements and a second row for maintaining their frequency.

Step 3: Now sort the elements according to their frequency and if two elements are of the same frequency remain them in the sorted order.

Code:

## C++ Code

``````#include <iostream>
#include <algorithm>
using namespace std;
// Function to sort 2d array by frequency
void sort2darray(int array2d[2][100], int k)
{
for (int i = 0; i < k - 1; i++)
{
for (int j = 0; j < k - 1 - i; j++)
{
if (array2d[1][j] < array2d[1][j + 1])
{
swap(array2d[1][j], array2d[1][j + 1]);
swap(array2d[0][j], array2d[0][j + 1]);
}
}
}
}
// Function to sort elements of array by frequency
void Sortele(int arr[], int n)
{
// Step 1: Sort the array
sort(arr, arr + n);
// Step 2: Create a 2d array
int arr2d[2][100];
int k = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
if (i == 0)
{
arr2d[0][k] = arr[i];
count = 1;
}
else if (arr[i] == arr[i - 1])
{
count++;
}
else
{
arr2d[1][k] = count;
count = 1;
k++;
arr2d[0][k] = arr[i];
}
}
arr2d[1][k] = count;
k++;

// Step 3: sort the 2d array according to frequency
sort2darray(arr2d, k);

// Step 4: Store the answer in original array
k = 0;
int i = 0;
while (i < n)
{
while (arr2d[1][k] > 0)
{
arr[i] = arr2d[0][k];
i++;
arr2d[1][k]--;
}
k++;
}
}
int main()
{
int n = 8;
int arr[] = {1, 2, 3, 2, 4, 3, 1, 2};
Sortele(arr, n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}
``````

Output:

2 2 2 1 1 3 3 4

Time Complexity: O(n^2)

Space Complexity: O(n)

## Java Code

``````import java.util.*;
public class Main {
// Function to swap elements
public static void swap(int[][] arr, int i, int j) {
int temp1 = arr[0][i];
arr[0][i] = arr[0][j];
arr[0][j] = temp1;

int temp2 = arr[1][i];
arr[1][i] = arr[1][j];
arr[1][j] = temp2;
}
// Function to sort 2d array by frequency
public static void sort2darray(int[][] array2d, int k) {
for (int i = 0; i < k - 1; i++) {
for (int j = 0; j < k - 1 - i; j++) {
if (array2d[1][j] < array2d[1][j + 1]) {
swap(array2d, j, j + 1);
}
}
}
}
// Function to sort elements of array by frequency
public static void Sortele(int[] arr, int n) {
// Step 1: Sort the array
Arrays.sort(arr, 0, n);
// Step 2: Create a 2d array
int[][] arr2d = new int[2][100];
int k = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
arr2d[0][k] = arr[i];
count = 1;
} else if (arr[i] == arr[i - 1]) {
count++;
} else {
arr2d[1][k] = count;
count = 1;
k++;
arr2d[0][k] = arr[i];
}
}
arr2d[1][k] = count;
k++;

// Step 3: sort the 2d array according to frequency
sort2darray(arr2d, k);

// Step 4: Store the answer in original array
k = 0;
int i = 0;
while (i < n) {
while (arr2d[1][k] > 0) {
arr[i] = arr2d[0][k];
i++;
arr2d[1][k]--;
}
k++;
}
}
public static void main(String args[]) {
int n = 8;
int[] arr = {1,2,3,2,4,3,1,2};
Sortele(arr, n);
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
``````

Output:

2 2 2 1 1 3 3 4

Time Complexity: O(n^2)

Space Complexity: O(n)

Solution 2: Optimal Approach (using hashing and sorting)

Approach:

STEP 1: Just store all elements on a map according to their count.

STEP 2: Store all elements of the map in a vector one by one.

STEP 3: Sort that vector according to its frequency.

STEP 4: Now print them or push them into the answer vector.

Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;
bool sortele(pair<int, int> a, pair<int, int> b)
{
if (a.second == b.second)
return a.first < b.first;
return a.second > b.second;
}
void Sortelementsbyfreq(int arr[], int n)
{
unordered_map<int, int> map;
for (int i = 0; i < n; i++)
{
map[arr[i]]++;
}
vector<pair<int, int>> vec;
for (auto it = map.begin(); it != map.end(); it++)
{
vec.push_back({it->first, it->second});
}
sort(vec.begin(), vec.end(), sortele);
for (int i = 0; i < vec.size(); i++)
{
while (vec[i].second > 0)
{
cout << vec[i].first << " ";
vec[i].second--;
}
}
cout << endl;
}
int main()
{
int arr[] = {3, 3, 5, 2, 1, 1, 2};
int n = 7;
Sortelementsbyfreq(arr, n);
return 0;
}
``````

Output: 1 1 2 2 3 3 5

Time Complexity – O(N) where N is the number of elements in the array

Space Complexity – O(N) for storing the elements in Map, vector

## Java Code

``````import java.util.*;
class Pair{
int first;
int second;
Pair(int first,int second)
{
this.first=first;
this.second=second;
}
Pair()
{

}
}
class TUF{
static void Sortelementsbyfreq(int arr[], int n)
{
HashMap<Integer, Integer> map=new HashMap<>();
for (int i = 0; i < n; i++)
{

map.put(arr[i],map.getOrDefault(arr[i],0)+1);
}
ArrayList<Pair> vec=new ArrayList<>();
for (int x:map.keySet())
{
}
Collections.sort(vec,(a,b)->{
if(a.second==b.second)
return a.first-b.first;
else
return b.second-a.second;
});
for (int i = 0; i < vec.size(); i++)
{
while (vec.get(i).second > 0)
{
System.out.print(vec.get(i).first+" ");
vec.get(i).second--;
}
}

}
public static void main(String args[])
{
int arr[] = {3, 3, 5, 2, 1, 1, 2};
int n = 7;
Sortelementsbyfreq(arr, n);

}
}``````

Output: 1 1 2 2 3 3 5

Time Complexity – O(N) where N is the number of elements in the array

Space Complexity – O(N) for storing the elements in Map, vector