# Sort elements by their frequency and index

Posted in

Vinay Khatri
Last updated on September 21, 2024

## Problem

Given an array of integers, sort them by their frequencies. If two elements have the same frequencies, sort them by their indices.

#### Sample Input

`1, 1, 2, 3, 3, 3`

#### Sample Output

`3, 3, 3, 1, 1, 2`

### Approach

We can make our custom comparator in this approach. The comparator should:

1. first compare the frequency of the two elements, if the frequency is the same,
2. compare it using indices.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

// Comparator function
bool comparator(tuple<int, int, int> const& x,
tuple<int, int, int> const& y)
{
// If two elements have different frequencies, then
// the one which has more frequency should come first
if (get<1>(x) != get<1>(y)) {
return get<1>(x) > get<1>(y);
}
// else element with lower index should be smaller one
else {
return get<2>(x) < get<2>(y);
}
}

void solve(int arr[], int n)
{
if (n < 2) {
return;
}

unordered_map<int, pair<int, int>> mp;

// append frequency of each array element into the map
// and index of its first occurrence in the array
for (int i = 0; i < n; i++)
{
if (mp.find(arr[i]) != mp.end()) {
mp[arr[i]].first++;
}
else {

mp[arr[i]] = make_pair(1, i);
}
}

// vector of tuple to store elements, frequency and first occurrence
vector<tuple<int, int, int>> vp;

for (auto it: mp)
{
pair<int, int> p = it.second;
vp.push_back(make_tuple(it.first, p.first, p.second));
}

// sort the elements using custom comparator
sort(vp.begin(), vp.end(), comparator);

int a, b, c, k = 0;
for (auto element: vp)
{
tie(a, b, c) = element;
for (int j = 0; j < b; j++) {
arr[k++] = a;
}
}
}

int main()
{
int a[] = {1, 1, 2, 3, 3, 3};
int n = sizeof(a) / sizeof(a[0]);

solve(a, n);

for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}

return 0;
}
```

#### Output

`3 3 3 1 1 2`

### Python Programming

```# Create class having three member variables
class Node:
def __init__(self, value, index, count=0):
self.value = value
self.index = index
self.count = count

# Function to sort elements by frequency and index
def solve(arr):
if arr is None or len(arr) < 2:
return

mp = {}

for i in range(len(arr)):
mp.setdefault(arr[i], Node(arr[i], i)).count += 1

values = [*mp.values()]
# Sort by custom comparator
values.sort(key=lambda x: (-x.count, x.index))

k = 0
for element in values:
for j in range(element.count):
arr[k] = element.value
k += 1

arr = [1, 1, 2, 2, 3, 3, 3]
solve(arr)
print(arr)```

#### Output

`[3, 3, 3, 2, 2, 1]`

### Java Programming

```import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Node implements Comparable<Node>
{
int value, count, index;

public Node(int value, int count, int index)
{
this.value = value;
this.count = count;
this.index = index;
}

public int compareTo(Node obj)
{
// If two elements have different frequencies
if (this.count != obj.count) {
return obj.count - this.count;
}

// If two elements have the same frequencies
return this.index - obj.index;
}
}

class Main
{

public static void solve(int[] arr)
{
if (arr.length < 2) {
return;
}

// insert frequency and first index of element
Map<Integer, Node> mp = new HashMap<>();
for (int i = 0; i < arr.length; i++)
{
mp.putIfAbsent(arr[i], new Node(arr[i], 0, i));
mp.get(arr[i]).count++;
}

// sort the values by custom comparator
List<Node> values = mp.values().stream()
.sorted()
.collect(Collectors.toList());

int k = 0;
for (Node data: values)
{
for (int j = 0; j < data.count; j++) {
arr[k++] = data.value;
}
}
}

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

solve(arr);
System.out.println(Arrays.toString(arr));
}
}```

#### Output

```[3, 3, 3, 2, 2, 1]
```