Majority Element

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 

 
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}



Here, we are sorting the entire array using sort() of Arrays class. Then, number at index position n/2 would be a majority element. There is no chance of wrong values in odd or even length. 

Below is another method using HashMap.

METHOD 2:

class Solution {

public int majorityElement(int[] nums) {
HashMap<Integer, Integer>list = new HashMap<Integer, Integer>();
int repeatLength = nums.length/2;
for(int num:nums){
list.put(num, list.getOrDefault(num, 0)+1);
if(list.get(num) > repeatLength){
return num;
}
}
return 0;
}
}



Try it on Leetcode

Here, we are going to use HashMap. We are storing repeatLength [i.e., n/2].

1) Iterate loop for each number and put in the list, where num is a key along by increasing count of each number occurrences as value. It can be done using getOrDefault() of Map class in Java.

2) In getOrDefault(key, value) - value we are setting at 0 and if we are adding key for first time it will return 0 [already set by us], then increment by 1 and add it in list.

3) Else it will return the stored value and increase by 1 and updating the list.

During these process, if there is any number greater than repeatLength it will be returned.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Happy Coding..!!