Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 
3.1.
Algorithm
4.
Explanation
5.
Implementation in C++
5.1.
Output
6.
Implementation in Java
6.1.
Output
7.
Implementation in Python
7.1.
Output
8.
Time Complexity 
9.
Auxiliary Space Complexity 
10.
Frequently Asked Questions
10.1.
What is hashing, explain with an example?
10.2.
What is a hash key in a data structure?
10.3.
How long does locating the second-largest element in an array typically takes? 
10.4.
What is the definition of a delete operation? 
10.5.
What exactly is a hash number?
11.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find The Top Three Repeated Elements In An Array

Author Kanak Rana
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A particular data structure called an array can hold a fixed-size sequential collection of identical-type elements. It is essential to think of an array as a collection of variables of the same type even though it is used to store a collection of data.

Let's solve the problem to find the top three repeated elements in an array.

This is a example of the given problems

Problem Statement

You are given an array of ‘n’ numbers with some repeated numbers in it, according to the problem to find the top three repeated elements in an array.

Example

First Example 

Input

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

Output

1 3 6

Explanation

In this case, 1, 3, and 6 are duplicated.
 

Second Example 

Input

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

Output

1 2 5

Explanation

In this case, 1, 2, and 5 are duplicated.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 

An array containing some integers is provided by user to us. Find the top three repeated elements in an array according to the problem. Therefore, counting and storing the frequencies of each element is the major goal. We'll be utilizing a map to guide us.

We will calculate the frequency of each element and then compare it to all other frequencies on the map to see which has a higher value, just like we did with the other three numbers.

Algorithm

  • Declare the unordered map. 
     
  • If less than three values are present, return.
     
  • Each component of the input array's frequencies should be counted, stored, and then added to the map.
     
  • Create the pair class objects and initialize them with the lowest possible integer value.
     
  • While moving throughout the map.
     
  • Verify whether the current key's frequency exceeds that of the objects it is allocated to.
     
  • If so, then move all of the keys and values to other Pair objects.
     
  • Copy the top three components.

Explanation

We will take an input array, Arr[]={1, 1, 1, 3, 2, 4, 2}. So the frequency of the elements will be: 

Example explanation
Example explanation
Example explanation

As we can see, the frequency of 1 is three times, 2 is two times and 4 and 3 both are one time.

So the most repeated elements are 1, 2 and 4 or 3.

Example explanation

So, the preferred output would be 1,2 and 3 or 1,2 and 4

Implementation in C++

/*
    A hashing based program in C++  for find the top three repeated elements in an array
*/
 
#include <bits/stdc++.h>
using namespace std;
 
 // The top three frequently repeated numbers function
 void duplicates(int given_arr[], int n)
 {    if (n < 3)
    {
        cout << "Wrong Input";
        return;
    }
 
    // Frequency of each element is counting.
    unordered_map<int, int> repeating;
    for (int i = 0; i < n; i++)
        repeating[given_arr[i]]++;
 
    // Set each variable's initial value
    pair<int, int> x, y, z;
    x.first = y.first = z.first = INT_MIN;
 
    for (auto front : repeating)
    {
 
        if (front.second > x.first)
        {
            z = y;
            y = x;
            x.first = front.second;
            x.second = front.first;
        }
 
        /*
            If the frequency of the element being considered is 
            not zero and  is larger
        */
        else if (front.second > y.first)
        {
            z = y;
            y.first = front.second;
            y.second = front.first;
        }
 
        /* 
            If the frequency of the current element is not 
            zero and it is not equal to the first or second 
            biggest element's frequency,it is greater than the
            third largest element's frequency.
        */
        else if (front.second > z.first)
        {
            z.first = front.second;
            z.second = front.first;
        }
    }
 
    cout << "The top three numbers are " << x.second << " "
         << y.second << " " << z.second;
}
 
int main()
{
    int n;
    cout<<"Enter the length of array :\n";
    cin>>n;
    cout<<"Enter the input digits for array :\n";
    int given_array[n];
    for(int i=0;i<n;i++)
    {
        cin>>given_array[i];
    }
    int x = sizeof(given_array) / sizeof(given_array[0]);
    duplicates(given_array, x);
    return 0;
}

Output

C++ program output

You can also read about the Longest Consecutive Sequence.

Implementation in Java

/*
    A hashing based program in java to find the top three repeated elements in an array
*/
import java.io.*;
import java.util.*;
 
class Pair
{
    int first, second;
}
 
class frequent
{
 
    // Top three frequently repeated numbers function
    static void duplicate3(int[] arr, int n)
    {
        // There ought to be at least two components.
        if (n < 3)
        {
            System.out.print("Wrong Input");
            return;
        }
 
        // Each element's frequency is counting.
        TreeMap<Integer, Integer> repeat_count = new TreeMap<>();
        for (int i = 0; i < n; i++)
            if (repeat_count.containsKey(arr[i]))
                repeat_count.put(arr[i], 1 + repeat_count.get(arr[i]));
            else
                repeat_count.put(arr[i], 1);
 
        // Set each variable's initial value
        Pair x = new Pair();
        Pair y = new Pair();
        Pair z = new Pair();
        x.first = y.first = z.first = Integer.MIN_VALUE;
 
        for (Map.Entry front : repeat_count.entrySet())
        {
            /*
                If the frequency of the current element is larger
                than the frequency of the first greatest element and not zero
            */
            if (Integer.parseInt(String.valueOf(front.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(front.getValue()));
                x.second = Integer.parseInt(String.valueOf(front.getKey()));
            }
 
            /*
                If the frequency of the current element is not zero
                and it is more than the frequency of the y element but
                lower than the frequency of the first greatest element
            */
            else if (Integer.parseInt(String.valueOf(front.getValue())) > y.first)
            {
           
                z.first = y.first;
                z.second = y.second;
                y.first = Integer.parseInt(String.valueOf(front.getValue()));
                y.second = Integer.parseInt(String.valueOf(front.getKey()));
            }
 
            /*
                If the frequency of the currently selected element
                is not zero and is larger than the third largest element
                while being less frequent than the first element and second largest element.
            */
            else if (Integer.parseInt(String.valueOf(front.getValue())) > z.first)
            {
 
                z.first = Integer.parseInt(String.valueOf(front.getValue()));
                z.second = Integer.parseInt(String.valueOf(front.getKey()));
            }
        }
 
        System.out.print("The top three numbers are " + x.second + " " + y.second + " " + z.second);
    }
 
   
    public static void main(String args[])
    {
        int n;
        int [] given_arr;
        Scanner input = new Scanner(System.in);
        System.out.println("Enter the length of array :\n");
       
        n = input.nextInt();
        given_arr = new int[n];
       
        System.out.println("Enter the input digits for array :\n");
        for(int i=0;i<n;i++)
        {
            int temp = input.nextInt();
            given_arr[i] = temp;
        }
       
        int x = given_arr.length;
        duplicate3(given_arr, x);
    }
}

Output

Java Program Output

Implementation in Python

# A hashing based program in python to find the top three repeated elements in an array

import sys

class Pair:
    def __init__(self,first = 0,second = 0):
        self.first = first
        self.second = second
   
# Top three frequently repeated numbers function.
def duplicate3(givenarray, n):

    # There ought to be at least two components.
    if (n < 3):
        print("Wrong Input")
        return

    # Frequency of each element is counted.
    givenarray.sort()
    repeat = {}
    for i in range(n):
        if (givenarray[i] in repeat):
            repeat[givenarray[i]] = 1 + repeat[givenarray[i]]
        else:
            repeat[givenarray[i]] = 1
            # Set each variable's initial value
            x = Pair()
            y = Pair()
            z = Pair()
            x.first = y.first = z.first = -sys.maxsize -1

    for curr,curr2 in repeat.items():
        # If the frequency of the current element is larger
        # than the frequency of the greatest element and not zero.
        if (int(curr2) > x.first):

            # the second- and third-largest updates
            z.first = y.first
            z.second = y.second
            y.first = x.first
            y.second = x.second
            x.first = int((curr2))
            x.second = int((curr))

        # If the frequency of the current element is not zero,
        # it is more than the frequency of the y element
        # but less frequent than the frequency of the
        # current element's largest neighbour.
        elif (int((curr2)) > y.first):
       
            z.first = y.first
            z.second = y.second
            y.first = int((curr2))
            y.second = int((curr))

        # If the frequency of the current element is not zero and
        # it is less frequent than the first element and
        # second-largest element while being more frequent than
        # the third-largest element.
        elif (int((curr2)) > z.first):

            # Modify values of z Number
            z.first = int((curr2))
            z.second = int((curr))

    print(f"The top three numbers are {x.second} {y.second} {z.second}")
    givenarray=[]
    n=int(input("Enter the length of array:\n"))
    print(f"Enter the input digits for array:\n")
    for x in range(0,n):
        z=int(input())
        givenarray.append(z)
        duplicate3(givenarray, n)

Output

Python Program Output

Time Complexity 

O(N), Where ‘N’ stands for the length of the array.

Reason: We were able to linearize the problem statement  "Find top three repeated in array" by significantly reducing the time complexity through hashmap.

Auxiliary Space Complexity 

O(N), Where ‘N’ stands for the length of the array.

Reason: In the worst-case scenario, ‘N’ key-value pairs will be stored. Therefore, the complexity of space is also linear.

Frequently Asked Questions

What is hashing, explain with an example?

Hashing is intended to solve the problem of efficiently finding or storing an item in a collection. For example, if we have a list of 10,000 English words and want to see if a specific word is on the list, it would be inefficient to compare the word with all 10,000 items until we find a match.

What is a hash key in a data structure?

A hash table is a data structure used to store key-value pairs. A hash function is used to perform arithmetic operations on the key. The output (also known as the hash value or hash) is the index of the key-value pair in the hash table.

How long does locating the second-largest element in an array typically takes? 

Picking the first and second members of the array in descending order will allow you to determine the greatest and second-largest integer quickly. The largest number will be its first element, while the second-largest number will be its second element. This solution has an O time complexity (n log n).

What is the definition of a delete operation? 

Deletion is the process of eliminating an existing element from an array and reorganizing all of its features. The delete action can be applied to one or more objects that meet the specified conditional expression. The delete operation can be combined with a list (of any kind), allowing the user to select the object(s) to be erased.

What exactly is a hash number?

A hash value, also known as a message digest, is a number generated from a string of text.

Conclusion

This article has gone through problems related to the array, that how to find the top three repeated elements in an array, Counting and storing the frequencies of each element is the major goal. We'll be utilizing a map to guide us and it will also reduce the time complexity. Check out our articles:


Check out the following problems - 

 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

 Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Thank you

Ninja, have a great time learning.

Previous article
Find Missing Elements of a Range
Next article
Find top k numbers in a stream
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass