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

Input: nums = [3,2,3]
Output: 3
Explanation: element 3 appeared 2 times and that is majority element.

Input: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation: element 2 appeared 4 times and that is majority element.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Solution using a HashMap to store count of each number appearance
Solution to follow-up question using 'Boyer-Moore' pattern searching algorithm

In this approach, we are going to iterate through elements of input array nums and store the count of each number and how many times it appeared into a HashMap and keep track of number that appeared more times.

import java.util.HashMap; public class MajorityElement { static int usingHashMapStoreCount(int[] nums) { HashMap<Integer, Integer> count = new HashMap<>(); int maxAppeared = 0;// to keep track of maximum number of times that a number appeared int max = 0; // to keep track of the number for(int num: nums) { int newVal = count.merge(num, 1, Integer::sum); if(newVal> maxAppeared) { maxAppeared = newVal; max = num; } } return max; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(n) since we are storing count mappping into a HashMap.

Boyer Moore's algorithm is an efficient algorithm for searching string patterns. We are going the same logic in this solution and for this problem it is easy to implement.

Implementation details

In this approach, we are going to create two variables count that we will use to keep track of maximum number of times a number is appeared so far and max is the number that appeared maximum number of times so far.

This approach will work based on the fact that a majority element always exists (number that appears more than n/2 times).

When the count is 0, we just update count = 1 and max to current number.
If the current number is same as max then we will increment count.
If the current number is not same as max then we will decrement count.
Finally, just return max.

Let's understand with an example, say nums = [2, 3, 2, 3, 2].

In the first step count =0, so we take number into max = 2 and count =1.
Next number is 3, and this is not same as max that we got so far, so decrement count, so it becomes count =0.
Next number is 2, and the count =0, so we update max =2 and count =1.
Next number is 3, and this is not same as max that we got so far, so decrement count, so it becomes count =0.
Next number is 2, and the count =0, so we update max =2 and count =1.
Now, notice that max variable holds number 2, and that is our answer, so return that.

import java.util.HashMap; public class MajorityElement { static int usingPatternSearch(int[] nums){ int count = 0; int max =0; for(int num: nums) { if (count == 0) { max = num; count =1; } else if(num == max) { count++; } else { count--; } } return max; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Implementation details

Complexity Analysis: