Majority element | Leetcode #169

This video explains a very interesting counting based array interview question which is to find the majority element in the array. It seems to be a very simple question at first glance but solving in linear time O(1) might get tricky. In this video, i have explained the intuition for solving this problem in just O(N) time and O(1) extra space. I have explained this problem in detail with much more in-depth example and intuition and the link for that is given below. At the end of this video, i have explained the CODE for which CODE LINK is given below, as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

SIMILAR PROBLEM:-

[aniruddhabhattacharya]

Simplest and the effective approach of solving these type of problems is map....
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int> mp;
for(int i=0;i<nums.size();i++){
mp[nums[i]]++;
}

int n = nums.size()/2;

for(auto itr: mp){
if(itr.second > n){
return itr.first ;
}
}
return -1;
}
};

[peter]

Explained very well bro thanks for the help

[Udzial]

Thanks very well explained. I can understand easiily. When i saw this first time at leet code it was little confusing.
you gave a good explanation. Thank you

[himanshupednekar]

I have use a different approach. I have first sorted the list and then return the ⌊ n/2 ⌋ th element from the sorted list.
Code in python is as follow:


class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]

[anilchaudhry]

This is actually called Moore's Voting Algorithm

[premjeetprasad]

this way a good idea for solving such problems in constant space

[rosonerri-faithful]

Excellent intuition Surya Sir🧡🧡. this is what is called "EXPLANATION". thank you Sir
class Solution {
public int majorityElement(int[] nums) {
int majority=nums[0];
int count=1;
for(int i=1;i<nums.length;i++)
{
if(nums[i]==majority)
count++;
else
count=count-1;
if(count==0)
{
majority=nums[i];
count=1;
}
}
return majority;
}
}
The Java Code for the same program

[anushree]

Can we say, the majority element is always the max occurred element in the array?

[fatimajaffal]

int majorityElement(vector<int>& nums) {

cin.tie(NULL);
unordered_map<int, int>v;
int n = nums.size();
int s = n/2;
for (int i = 0; i < n; i++) {
v[nums[i]]++;
if(v[nums[i]] > s) return nums[i];
}
return -1;

}


I just solved it using map, same time complexity O(n) but absolutely different in space complexity, nice approach.

[abhishekghosh]

In this algorithm, what happens if the majority element is not at the end of the array. Eg. The array becomes [1, 1, 1, 1, 2, 3]

[yesterdayoncemore]

Hi, thank you for this interesting video. I actually found a potential issue of this solution. E.g, if the array is [1, 2, 1, 3], the majority would be 1. However, using your strategy. 3 will replace 1 as the majority. See your video around 5:09. 1 was replaced by 3 because the count was 1 for 1 at that time.

[smirkedShoe]

Can you explain why this Moore algorithm actually works ?

[abhinavminocha]

Please upload more videos on Graphs and Trees.

[vimalradadiya]

What approach if we won't assume that elements always exist in array

[fahizmohd]

sir, we can find it with dictionary as value increment and find max of that

[itsyash]

At 1:39
Sir the element '1' has occurred max number of times so why there is no majority element??

[sanjibkumargope]

Can You please make a video on, how to solve remainder type question like 10^9+7 for C++ language.

[chandrukumar]

class Solution:
def majorityElement(self, nums: List[int]) -> int:
l=len(nums)
l=l//2
n=set(nums)
for i in n:
if nums.count(i)>l:
return i

[uwu-dmvb]

majority = 0
count = 0
for i in nums:
if i!=majority and count!=0:
count-=1
if i==majority:
count+=1
if count == 0:
majority = i
count = 1
return majority

[nonameeee]

Easy sol
Arrays.sort(nums);
return nums[ nums.length/2];