Find Majority Element in an Array

Majority element in an array Array[] of size n is an element that appears more than n/2 times.

Write a function which takes an array and gives the majority element (if it exists), otherwise return -1.

Input : 2 4 5 5 5 0
Result : 5

Input : 3 5 6 9 6 7
Result : -1

Method 1: (n2 run time)

The basic solution is to have two loops and keep track of count for current element. If the count becomes greater than n/2 then break the loops and return the element. If loop ends completely then simply return -1.

Time Complexity: O(n*n).
Auxiliary Space : O(1).

Method 2:

1. Sort the Array.
2. Start from middle element and count on both way if left or right element is equal to middle element.
If the count is greater than n/2 then break and return the element.
Logic: If any number exist more than n/2 time, it will must come in middle of sorted array.

Time Complexity: O(n*logn) [ Based on sorting algorithm]
Auxiliary Space : O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |