Table of Contents

## Problem Statement

We are given an array of integers. We need to return the integer which occurs more than ⌊N / 2⌋ time in the array where ⌊ ⌋ is the floor operator. This element is called the majority element. Note that the input array always contains a majority element.

### Example

Array = {1 , 3 , 3 , 3}

3

**Exaplanation**: ⌊N / 2⌋ = 4 / 2 = 2. And the integer ‘3’ occurs 3 times in the array.

Array = {1 , 1 , 2}

1

**Explanation**: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. And ‘1’ occurs 2 times in the array.

## Approach(Hashtable)

We can store the frequency of every element in the array in a hash table. It then becomes easy to check for an integer having frequency > ⌊N / 2⌋.

### Algorithm

- Initialize a hash table to store the frequency of integers in the array:
*frequency* - For every element,
*i*, in the array:- Increment
*frequency[i]*or set*frequency[i] = 0*if it is not in the table already - If
*frequency[i]*> N / 2:- return i

- Increment
- Return -1 (to avoid compilation error)
- Print the result

### Implementation of Majority Element Leetcode Solution

#### C++ Program

#include <bits/stdc++.h> using namespace std; int majorityElement(vector <int> &a) { int majorityCount = ((int) a.size()) / 2; unordered_map <int , int> frequency; for(int &i : a) { if(++frequency[i] > majorityCount) return i; } return -1; } int main() { vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2}; cout << majorityElement(a) << '\n'; return 0; }

#### Java Program

import java.util.*; class majority_element { public static void main(String args[]) { int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2}; System.out.println(majorityElement(a)); } static int majorityElement(int[] a) { HashMap <Integer , Integer> frequency = new HashMap<>(); for(int i = 0 ; i < a.length ; i++) { frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1); if(frequency.get(a[i]) > a.length / 2) return a[i]; } return -1; } }

2

### Complexity Analysis of Majority Element Leetcode Solution

#### Time Complexity

**O(N) **as we traverse the array once to find the majority element. **N** = size of the array.

#### Space Complexity

**O(N) **as the maximum number of distinct elements in the array can be: **N – ⌊N / 2⌋ **as the majority element occupies at least **⌊N / 2⌋ **indices. Therefore, the space complexity is linear.

## Approach(Boyer-Moore Voting Algorithm)

This problem is a nice illustration of how can we find a majority element in a stream of elements. The Boyer-Moore Voting algorithm is used to find the element that occupies more than ⌊N / 2⌋ places in a sequence. This algorithm maintains a *candidate* and its *count* in the array. We run a single pass of the array with *candidate* = -1 and *count* = 0. If any element in the array is the *candidate*, we increment *count. *Otherwise, we decrement it. If the count becomes zero, we change the *candidate* and set its *count* back to 0.

In order to understand its functioning, follow the example below:

This algorithm considers the process as an election and first decides a candidate. The one who gets the most votes is the majority candidate. In the above example, we choose a candidate as 1 initially, but as we reach index 4 in the array, we observe that count = 0, which means that we have seen as many candidates as non-candidates. So, we choose the current element as a candidate and continue the process. Since we are **guaranteed** to have a majority element in the array, the last candidate we are left with will be the majority element.

### Algorithm

- Initialize two variables:
*candidate*and*cnt*to store the candidate and its frequency for respective iterations - Now, for every element
*i*in the array:- If
*cnt*is equal to zero:- update:
*candidate = i*

- update:
- If
*i*is equal to*candidate*:- increment
*cnt*:*cnt++*

- increment
- Else:
- Decrement
*cnt*:*cnt–*

- Decrement

- If
- Return
*candidate* - Print the result

### Implementation of Majority Element Leetcode Solution

#### C++ Program

#include <bits/stdc++.h> using namespace std; int majorityElement(vector <int> &a) { int candidate = -1 , cnt = 0; for(int &i : a) { if(cnt == 0) candidate = i; cnt += (candidate == i) ? 1 : -1; } return candidate; } int main() { vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2}; cout << majorityElement(a) << '\n'; return 0; }

#### Java Program

import java.util.*; class majority_element { public static void main(String args[]) { int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2}; System.out.println(majorityElement(a)); } static int majorityElement(int[] a) { int candidate = -1 , cnt = 0; for(int i = 0 ; i < a.length ; i++) { if(cnt == 0) candidate = a[i]; cnt += (candidate == a[i]) ? 1 : -1; } return candidate; } }

2

### Complexity Analysis of Majority Element Leetcode Solution

#### Time Complexity

**O(N) **as we traverse the whole array once. Here, **N** = size of the array.

#### Space Complexity

**O(1)** as we use constant memory space.