Sort elements by their frequency and index

Posted in

Sort elements by their frequency and index
vinaykhatri

Vinay Khatri
Last updated on November 30, 2023

    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:

    Leave a Comment on this Post

    0 Comments