Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach (using nested loops)
2.1.
Pseudocode
2.2.
Implementation
2.2.1.
Time complexity 
2.2.2.
Space complexity 
3.
Boyer-Moore Majority Vote Algorithm
3.1.
Pseudocode
3.2.
Implementation 
3.2.1.
Time complexity 
3.2.2.
Space complexity 
4.
Frequently Asked Questions
4.1.
Is this problem, finding the element in a sorted array whose frequency is greater than or equal to n/2 the same as finding the majority element with a maximum frequency in a sorted array?
4.2.
What should I return if there is no element whose frequency is greater than or equal to n/2? 
4.3.
What is Boyer-Moore Majority Vote Algorithm?
4.4.
What is the time complexity of the Boyer-Moore Majority Vote Algorithm approach?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find Element in a Sorted Array whose Frequency is Greater than or Equal to n/2

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Finding an element in a sorted array whose frequency is greater than or equal to n/2 is an array searching problem. It is one of the very basic problems that have many approaches. That’s why it had been asked in many interviews. It had been asked in the Microsoft, Google, Amazon, and Yahoo interview round for the role of software engineers/developers. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach of the programmer. 

In this article, we are going to discuss two methods to solve this problem find element in a sorted array whose frequency is greater than or equal to n/2; the first is the brute force or naive approach, and the second is by using Boyer-Moore Majority Vote Algorithm.

Also see, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Find an element in a sorted array whose frequency is greater than or equal to n/2, in here we are given a sorted array A[] of n elements. We need to find and return the number that appears more than n/2 times.

Sample Examples


Example 1:

Input: A[] = 

                                             

Output:

 3

Explanation: In the above example, the total number of elements in the array is 8, and the element which is appearing more than n/2 or 8/2=4 times is 3. That’s why the output is 3.

 

Example 2:

Input: A[] =

                                           

Output

8

Explanation: In the above example, the total number of elements in the array is 10, and the element which is appearing more than n/2 or 10/2=5 times is 8. That’s why the output is 8.

 

Example 3:

Input: A[] = 

                                                      

Output:

 5

Explanation: In the above example, the total number of elements in the array is 6, and the element which is appearing more than n/2 or 6/2=3 times is 5. That’s why the output is 5.

Brute Force Approach (using nested loops)

For this problem, a simple brute force approach would be to use nested loops and count the frequency of each element. When we reach an element with a frequency greater than n/2, we have found our majority element.

Pseudocode

    for i = 0 to n-2
        int count = 1
        for j = i+1 to n-1  
            if  A[i] is equal to A[j] 
            count = count + 1
       if  count > n/2 
       return A[i]

Implementation

#include <iostream>
using namespace std;

int findMajorityElement(int A[], int n)
{      
    for (int i = 0;i< n-2;i++ )
    { int count = 1;
        for ( int j = i+1;j< n-1;j++ )
        {
            if ( A[i] == A[j] )
                count = count + 1;
        }
       if ( count > n/2 )
            return A[i];
    }
   return -1;
}

int main()
{
	int arr[] = {1,3,3,3,3,3,5,9};
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << findMajorityElement(arr, n);
	return 0;
}


Output

3

Time complexity 

The time complexity of this approach is O(N^2). Since we are using nested loops and iterating each loop N time.

Space complexity 

The space complexity of this approach is O(1). Since we are not using any extra space.

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

Boyer-Moore Majority Vote Algorithm

If the majority element is guaranteed to exist, the Boyer-Moore Majority Vote Algorithm finds it. To confirm, we will simply check the frequency of the element discovered by this algorithm.

The algorithm's intuition is that because the majority element occurs more than n/2 times, its frequency is greater than the sum of all other elements. As a result, we can cross out one non-majority element for each occurrence of the majority element.

Pseudocode

    initialize max_index = 0, count = 0
    for i = 0 to n-1 
        if A[i] is equal to A[max_index] )
           then count= 1 + count
        ELSE
            count = 1- count
        if count is equal to 0 
           then max_index = i
            And afterwards count = 1
     
    count = 0
    for i = 0 to n-1 
        if  A[i] is equal to A[max_index] 
           then count = 1 + count
    if  count > n/2 
        return the A[max_index]
    ELSE
        return -1

Implementation 

#include <iostream>
using namespace std;

int findMajority(int A[], int n)
{
    int max_index = 0, count = 0;
    for(int i = 0;i< n-1;i++ )
    {
        if ( A[i] == A[max_index] )
            count += 1;
        else
            count -= 1;
        
        if ( count == 0 )
        {
            max_index = i;
            count = 1;
        }
    }
    count = 0;
    for ( int i = 0; i<n-1 ;i++ )
        if ( A[i] == A[max_index] )
            count += 1;
    
    if ( count > n/2 )
        return A[max_index];
    else
        return -1;
}


int main()
{
	int arr[] = {1,3,3,3,3,3,5,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << findMajority(arr, n);
	return 0;
}

Output

3

Time complexity 

The time complexity of this approach is Linear traversal of array + Finding frequency of A[max_index] = O(n) + O(n) = O(n).

Space complexity 

The space complexity of this approach is O(1).

Frequently Asked Questions

Is this problem, finding the element in a sorted array whose frequency is greater than or equal to n/2 the same as finding the majority element with a maximum frequency in a sorted array?

No, in this problem, we are finding an element whose frequency is greater than or equal to n/2.

What should I return if there is no element whose frequency is greater than or equal to n/2? 

In this case, we can simply return -1, assuming that “-1” will never be an element of the input array.

What is Boyer-Moore Majority Vote Algorithm?

The Boyer-Moore voting algorithm is a popular optimal algorithm for determining the majority element among given elements with more than N/ 2 occurrences.

What is the time complexity of the Boyer-Moore Majority Vote Algorithm approach?

The time complexity of Boyer-Moore Majority Vote Algorithm approach is Linear traversal of array + Finding frequency of A[max_index] = O(n) + O(n) = O(n).

Conclusion

This article extensively discussed the problem of find element in a sorted array whose frequency is greater than or equal to n/2.

We hope this blog has helped you enhance your knowledge regarding the array searching problems. After reading about the find element in a sorted array whose frequency is greater than or equal to n/2 problem’s approach, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered.

Recommended Problem - Merge K Sorted Arrays

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Count of only Repeated Element in a Sorted Array of Consecutive Elements
Next article
Find the minimum element in a sorted and Rotated Array
Live masterclass