## Thursday, May 19, 2022

### Easy_Question25 : Majority Element

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

Example 1:

`Input: nums = [3,2,3]Output: 3`

Example 2:

`Input: nums = [2,2,1,1,1,2,2]Output: 2`

#### Approach : Boyer-Moore Voting Algorithm

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

Now, the majority element is `5` (we changed the last run of the array from `7`s to `5`s), but our first candidate is still `7`

In this case, our candidate is not the true majority element, but we still cannot discard more majority elements than minority elements (this would imply that `count` could reach -1 before we reassign `candidate`, which is obviously false).

Therefore, given that it is impossible (in both cases) to discard more majority elements than minority elements, we are safe in discarding the prefix and attempting to recursively solve the majority element

problem for the suffix. Eventually, a suffix will be found for which `count` does not hit `0`, and the majority element of that suffix will necessarily be the same as the majority element of the overall array

``````public class Solution {
public static void main(String[] args) {

//array of 10 numbers
int arr[] = new int[]{2,2,1,1,1,2,2};
System.out.println("majorityElement is :" +majorityElement(arr));
}
public static int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}Complexity Analysis
Time complexity : O(n)
Boyer-Moore performs constant work exactly n times, so the algorithm runs in linear time.
Space complexity : O(1)
Boyer-Moore allocates only constant additional memory.``````

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS