Majority Element

[AdvancedNoob]

Nice solution @Kevin. This can also be solved in O(n) time with O(1) space. The hashmap approach (mentioned in the video) takes O(n) time and O(1) space, but if we use Boyer-Moore's algorithm, we don't need hashmap for that.

Solution in C#:
public class Solution {
public int MajorityElement(int[] nums) {

//Can be solved using Boyer-Moore's algorith
int major = nums[0];
int count = 1;

for (int i = 1; i < nums.Length; i++){
if(major == nums[i]){
count++;
}
else{
count--;
}
if(count == 0){
major = nums[i];
count++;
}
}
}
}

[dejavukun]

I used binary search twice to solve this problem. Basically if the majority element is there, then i find the last occurence and first occurences and subtract them to check if greater than n//2. In the edge case that the majority element is filled in the left or right part, i check the mid - first or last - miss value. It works in nlogn because array needs to be sorted.

[chirag]

I solved this same problem (before looking at your solution) by using the same logic of HashMap that you used except I created 2 for loops, one for first half and one for second half of the array. The first half does not need the if condition that you've put and can do away with just the else part. The second array needs both since that is when the count of the 'majority element' can reach more than n / 2.

[AnshumanKumar]

We can use Bit Manipulation for this too.
```
class Solution {
public int majorityElement(int[] nums)
{
int res = 0;
// HashMap<Integer, Integer> hashMap = new HashMap<Integer>
for (int i = 0; i <= 31; i++ )
{
int pattern = 1<<i;
int count= 0;
for (int j = 0; j < nums.length ; j++ )
{
int x= pattern & nums[j];
// System.out.println(nums[j] + " " + pattern + " " + x);
if ((pattern & nums[j]) == pattern)
{
count++;
}
}

if (count > nums.length/2)
{
res |= pattern;
}
}
return res;
}
}
```

[dipankarbhatia]

If I try doing this with normal for loop, it doesn't work but with for-each loop it works. Can anybody tell me what is happening?

[tennesseefoodie]

Hi Kevin! Thank you so much for your videos. Can you explain line 9 again about why it is map.get(i) plus 1 ? Thanks!

[subhajitdas]

Well if Google is asking this problem then probably solving in O(n) of space and time complexity won't cut it. Use Boyer-Moore Voting Algorithm to solve this problem

[reviliant]

Hello, for the set [3, 3, 3, 5, 6, 7, 8, 9] what will be the majority element? Leetcode provides the answer as 8. I think the answer should be 3 if I am not mistaken...Thanks in advance.. @Kevin

[ishan_kumar]

what is the use of specifically taking care of single element case ? Can't HashMap itself take care of that ?

[ishan_kumar]

How about sort the array and then return the middle value of the array ? :xD

[geetusharma]

Can anyone please explain line 12 in detail? . What are we doing in line 12 and why ?

[matthall]

How about the bit manipulation method for solving it? Far more interesting.

[book]

how did you guys know about HashMap.getOrDefault?? I can't even find that method in the java api for hashmap or anywhere else for that matter.

[TheTURK]

Thumbnail says passing the google interview. I watched and did not pass. SCAM.

[sidhantmanchanda]

Can you tell me how to get started with DS and algorithms