Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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:

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.

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;
}

/*
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

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

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: