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 AnalysisTime 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.