Sort elements by their frequency and index

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]

People are also reading:

• Hybrid QuickSort Algorithm
• Quicksort using Dutch National Flag Algorithm
• Quicksort algorithm using Hoare’s partitioning scheme
• In-place vs out-of-place algorithms
• Minimum Edit Distance
• The Stock Span Problem
• Print Triangle Using * Character
• Subset Sum Problem
• Reverse a Linked List
• Maximum size square sub-matrices with all 1’s