Problem

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.

Definition

Majority Element: If an element appears more than n/2 times in array where n is the size of the array.

Examples

1
2
3
4
5

int [] arrA = {1,3,5,5,5,5,4,1,5};
Output: Element appearing more than n/2 times: 5

int []arrA = {1,2,3,4};
Output: No element appearing more than n/2 times

Follow up

Waht if we cannot assume that majority element always exists in an array.

Solution

This post goes through general solution - but we already have best solution: Majority Element - Boyer–Moore majority vote algorithm

Method 1 - Brute Force or Naive

Use nested for loops and count each element and if count>n/2 for each element. Time Complexity: O(n^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int majorityElement(int[] nums) {
	boolean found = false;
	for (int i = 0; i<nums.length; i++) {
		int x = nums[i];
		int count = 1;
		for (int j = i + 1; j<nums.length; j++) {
			if (x == nums[j])
				count++;
		}
		if (count > nums.length / 2) {
			return x;
		}
	}
	return -1;
}

Method 2 - Hashmap

  • Store the count of each element in Hash map.
  • Iterate through hash map and check if any element has count >n/2

Time Complexity: O(n), Space Complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int majorityElement(int[] nums) {
	boolean found = false;
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer> ();
	for (int i = 0; i<nums.length; i++) {
		if (map.containsKey(nums[i])) {
			int count = map.get(nums[i]);
			map.put(nums[i], ++count);
		} else
			map.put(nums[i], 1);
	}

	Set set = map.keySet();
	Iterator<Integer> iterator = set.iterator();
	while (iterator.hasNext()) {
		int key = iterator.next();
		if (map.get(key) > nums.length / 2) {
			return key;
		}
	}
	if (!found)
		return -1;
}

Method 3 - Sorting

We can sort the array first, which takes time of nlog(n). Then scan once to find the longest consecutive substrings.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int majorityElement(int[] nums) {
	if (num.length == 1) {
		return nums[0];
	}

	Arrays.sort(nums);

	int prev = nums[0];
	int count = 1;
	for (int i = 1; i<num.length; i++) {
		if (nums[i] == prev) {
			count++;
			if (count > nums.length / 2) return nums[i];
		} else {
			count = 1;
			prev = nums[i];
		}
	}

	return 0;
}

Method 4 - Sorting but Much Simpler

Thanks to SK. His/her solution is much efficient and simpler. Since the majority always take more than a half space, the middle element is guaranteed to be the majority. Sorting array takes nlog(n). So the time complexity of this solution is nlog(n). Cheers!

1
2
3
4
5
6
7
8

public int majorityElement(int[] nums) {
	if (nums.length == 1) {
		return nums[0];
	}

	Arrays.sort(nums);
	return num[nums.length / 2];
}

Method 5 - Vote Algorithm

Majority Element - Boyer–Moore majority vote algorithm