Majority Element (DSA)

Problem statement:(👈click here for GFG)

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

 Example 1:

Input:
N = 3 
A[] = {1,2,3} 
Output:
-1
Explanation:
Since, each element in 
{1,2,3} appears only once so there 
is no majority element.

Example 2:

Input:
N = 5 
A[] = {3,1,3,3,2} 
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is 
the majority element.

Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
 

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 

Constraints:
1 ≤ N ≤ 107
0 ≤ Ai ≤ 106

Solution:

Approach:

One way to solve this problem is by using the Boyer-Moore majority vote algorithm, which works as follows:

• Initialize a variable 'count' to 0 and a variable 'candidate' to -1

• Traverse the array, for each element 'num' do:

• a. If 'count' is 0, set 'candidate' to 'num'

• b. If 'num' is equal to 'candidate', increment 'count' by 1, otherwise decrement 'count' by 1

• After traversing the array, the 'candidate' variable should contain the majority element. To check if it's really the majority element, traverse the array again and count its occurrences. If it appears more than N/2 times, return it, otherwise return -1.

• The time complexity of this algorithm is O(N) and the space complexity is O(1).

Here's the implementation in JavaScript:

function majorityElement(arr, N) {

let count = 0;

let candidate = -1;

for (let i = 0; i < N; i++) {

if (count === 0) {

candidate = arr[i];

}

if (arr[i] === candidate) {

count++;

} else {

count--;

}

}

count = 0;

for (let i = 0; i < N; i++) {

if (arr[i] === candidate) {

count++;

}

if (count > N/2) {

return candidate;

}

}

return -1;

}

2nd Approach:

The given problem can be solved by using a hash table (JavaScript object) to keep track of the frequency of each element in the array. We can iterate through the array and count the frequency of each element. Once we have the frequency of all the elements, we can iterate through the hash table to find the element that appears more than N/2 times in the array. If no such element exists, we return -1.

Here is the step-by-step approach:

• Initialize an empty object obj to keep track of the frequency of each element.

• Iterate through the input array a using a for loop, from i = 0 to i < size.

• For each element a[i], check if it exists as a key in the object obj.

• If the key a[i] does not exist in obj, set obj[a[i]] = 1.

• If the key a[i] already exists in obj, increment the value of obj[a[i]] by 1.

• Once we have counted the frequency of all elements in the array, iterate through the keys of obj using a for...in loop.

• For each key key, check if its value is greater than size/2.

• If the value of obj[key] is greater than size/2, return the key key.

• If no key exists with a value greater than size/2, return -1.

//your code here

        let obj = {};

        for(let i = 0; i < size; i++){

            let key = a[i];

            if(obj[key] === undefined){

                obj[key] = 1;

            }

            else{

                obj[key]++;

            }

        }

        for(let key in obj){

            if(obj[key] > size/2){

                return key;

           }

This algorithm has a time complexity of O(N) as we iterate through the array only once, and a space complexity of O(N) to store the frequency of each element in the hash table. However, we can optimize the space complexity to O(1) by using the Boyer-Moore majority vote algorithm, which is a linear time algorithm with constant space complexity.

Thank you,

Learning is a never-ending process, and every day is an opportunity to learn something new. Keep exploring, keep pushing your limits, and keep striving towards your goals. Remember that every small step counts, and even the smallest progress is worth celebrating. Don't be afraid to ask questions, seek guidance, and learn from others. With dedication and hard work, you can achieve anything you set your mind to. So keep learning, keep growing, and keep shining!