# majority-element

Majority Element

## Problem Description

``````Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

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

## Solution

### Solution 1 -- HashMap

Using HashMap to store each element with its frequency as pair.

• iterate through array nums, add each number and its frequency into map

• after add into map, check whether current element frequency already greater than [n/2],

• if already, then terminate return current element.

• if not, continue.

since it is already assumed that array is non-empty, and always has majority element exist, so during iterate, majority element must find.

### Complexity Analysis

Time Complexity: `O(N)`

Space Complexity: `O(N)`

• N - length of array nums

### Code

``````class Solution {
public int majorityElement(int[] nums) {
int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
// check current element frequency
if (map.get(num) > len / 2) return num;
}
// should not be reached
return 0;
}
}``````

### Solution 2 -- Boyer-Moor voting algorithm

Assume that we maintain a candidate and count, iterate through array nums:

• We check count, if we found count == 0, reset candidate = num (current element)

• at the same time, we check current element num == candidate,

• if num == candidate, then count + 1;

• if num != candidate, then count - 1

• at last, remain candidate is majority element.

### Complexity Analysis

Time Complexity: `O(N)`

Space Complexity: `O(1)`

• N - the length of array nums

### Code -- Boyer-Moor voting algorithm

``````class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = nums[0];
for (int num : nums) {
// check current count, if count = 0, reset candidate to current element
if (count == 0) candidate = num;
// calculate count
count += candidate == num ? 1 : (-1);
}
// last candidate is majority element
return candidate;
}
}``````

Last updated