Problem

Submissions

Hints & solutions

Discuss

MaxFreq_Element

Moderate

0/80

Average time to solve is 15m

Contributed by

4 upvotes

Asked in company

Problem statement

You are given an array/list 'ARR' of size ‘N’. It contains elements from 0 to 'K - 1' such that 'K' <= 'N'.In this array, we have to find a number that appears maximum no of times. If there is more than one such number, return the maximum one.

Follow Up:

Try to do it O(N) time complexity and O(1) space complexity.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first line of each test case contains two integers ‘N’ and ‘K’, where ‘N' is the size of the array.

The second line contains ‘N’ single space-separated integers representing the elements of the array.

Output Format

 For each test case, return the maximum occurring integer in an array.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= 'T’ <= 50
1 <= 'N’ <= 10000
1 <= 'K' <= n
0 <= ARR[i] <= K-1 ∀ i(1,N)

Time Limit: 1sec

Sample Input 1

2
4 2 
1 1 1 0
6 3
1 1 2 2 0 0

Sample Output 1:

1
2

Explanation:-

For the first case:-
   1 is occurring 3 times.
   0 is occurring 1 time.
   So 1 is the answer.

For second case:-
   1,0,2 are all occurring 2 times but the maximum is 2.

Sample Input 2

2
4 1 
0 0 0 0
6 5
1 2 3 4 0 0

Sample Output 2:

0
0

Hint 1

Hint 2

Hint 3

Use brute force approach.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

Approach:-The key idea is to count the frequencies of all elements of the array. For every, ‘i’ from 1 to ‘N’ count the number of times the element A[i] is appearing from ‘i’ to ‘N’.

Algorithm:

Create two-variable 'MAX_NO' and 'MAX_FREQ' both initialize to 0.
For every ‘i’, 0 to ‘N-1’ count the number of times A[i] is appearing from ‘i’ to ‘N-1’.
If the count of A[i] is greater than 'MAX_FREQ' then update the 'MAX_FREQ' to count of A[i] and 'MAX_NO' to A[i]
If the count of A[i] is equal to 'MAX_FREQ' then 'MAX_NO' will be updated to A[i] if A[i] is greater than A[i].

Time Complexity

O(N^2), where ‘N’ is the size of the array.

For every ‘i’ we calculate the frequency of A[i] from ‘i’ to N-1 which takes O(N) time. Hence time complexity is O(N^2)

Space Complexity

O(1).

We use constant space to solve this.

(100% EXP penalty)

MaxFreq_Element

Console