Find top three repeated in array

The problem “Find top three repeated in array” states that you are given an array of n numbers with some repeated numbers in it. Your task is to find out the top 3 repeated numbers in an array.

Example

[1,3,4,6,7,2,1,6,3,10,5,7]

1 3 6

Explanation

Here 1,3 and 6 are repeated twice.

[2,4,2,1,5,6,8,5,3,9,0,1]

1 2 5

Explanation

Here 1,2 and 5 are repeated twice.

Algorithm to find top three repeated elements

1. Declare the map and the user-defined class called Pair.
2. Return if there are not at least three values present.
3. Count and store the frequencies of each element of the input array and put it into the map.
4. Create the objects of pair class and initialize it with the minimum value of an integer.
5. While traversing the map.
   1. Check if the frequency of the current key is greater than the objects assigned.
   2. If true, then shift all the keys and values to other objects of Pair.
6. Print the top three elements.

Explanation

We are given an array with some integers stored in it. The problem says that find out the top 3 repeated elements. So, our main idea is to count and store the frequencies of each element. We will be doing it using a map. Then comes another idea that is to declare a class and use that class’s objects to check and store our values which can be our output.

We are going to count each element frequency and then later compare with every other frequency in the map which is a greater number like we used to find out the bigger no in three other numbers.

Let us consider an example and understand this.

arr[ ]={ 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 }

Starting with counting the frequencies of each element present in the array. We will end up building a map in which, all of the elements and their frequencies are stored. Our map will consist of the following values:

Freq= {1:3, 2:2, 4:1, 9:4,15:3,9:4}

We have all we need, in all of this we just need to find out the top 3 repeated numbers. For that, we initialize the value of objects of pair class with the minimum value of the integer. We will traverse each of the keys and their frequency. Then compare with the objects as x.first, y.first, z.first. And in the end, we print the top 3 repeated elements in an array.

Code

C++ code to find top three repeated in array

#include <bits/stdc++.h>
using namespace std;
void getRepeatedNumbers(int arr[], int n)
{
    if (n < 3)
    {
        cout << "INVALID !! PLEASE ENTER CORRECT INPUT";
        return;
    }
    unordered_map<int, int> fre;
    for (int i = 0; i < n; i++)
        fre[arr[i]]++;

    pair<int, int> x, y, z;
    x.first = y.first = z.first = INT_MIN;

    for (auto val : fre)
    {
        if (val.second > x.first)
        {
            z = y;
            y = x;

            x.first = val.second;
            x.second = val.first;
        }
        else if (val.second > y.first)
        {
            z = y;

            y.first = val.second;
            y.second = val.first;
        }
        else if (val.second > z.first)
        {
            z.first = val.second;
            z.second = val.first;
        }
    }
    cout << "Top three repeated elements are  "<< x.second << " " << y.second<< " " << z.second;
}
int main()
{
    int arr[] = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getRepeatedNumbers(arr, n);
    return 0;
}

Top three repeated elements are  9 15 1

Java code to find top three repeated in array

import java.io.*;
import java.util.*;

class Pair
{
    int first, second;
}
class topThreeRepeatedNumber
{
    public static void getRepeatedNumbers(int[] arr, int n)
    {
        if (n < 3)
        {
            System.out.print("INVALID !! PLEASE ENTER CORRECT INPUT");
            return;
        }
        TreeMap<Integer, Integer> freq = new TreeMap<>();

        for (int i = 0; i < n; i++)
        {
            if (freq.containsKey(arr[i]))
                freq.put(arr[i], 1 + freq.get(arr[i]));
            else
                freq.put(arr[i], 1);
        }

        Pair x = new Pair();
        Pair y = new Pair();
        Pair z = new Pair();
        x.first = y.first = z.first = Integer.MIN_VALUE;

        for (Map.Entry val : freq.entrySet())
        {
            if (Integer.parseInt(String.valueOf(val.getValue())) > x.first)
            {

                z.first = y.first;
                z.second = y.second;
                y.first = x.first;
                y.second = x.second;

                x.first = Integer.parseInt(String.valueOf(val.getValue()));
                x.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > y.first)
            {
                z.first = y.first;
                z.second = y.second;

                y.first = Integer.parseInt(String.valueOf(val.getValue()));
                y.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > z.first)
            {
                z.first = Integer.parseInt(String.valueOf(val.getValue()));
                z.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
        }

        System.out.println("Top three repeated elements are " + x.second + ", "+ y.second + ", " + z.second);
    }
    public static void main(String args[])
    {
        int[] arr = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
        int n = arr.length;
        getRepeatedNumbers(arr, n);
    }
}

Top three repeated elements are 9, 1, 15

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Because of using Hashmap, we were able to reduce the time complexity by a significant factor making the problem “Find top three repeated in array” linear.

Space Complexity

O(n) where “n” is the number of elements in the array. In the worst-case, we will be storing n key-value pairs. Thus the space complexity is also linear.