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

Example 1

1
2

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

Example 2

1
2

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

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Follow up

  1. Could you solve the problem in linear time and in O(1) space?
  2. What 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