Majority element | Leetcode

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 :)
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEM:-
Majority element (BitMasking) : • Majority element in an...
Moore voting algorithm: • Moore voting algorithm

[@aniruddhabhattacharya807]

Simplest and the effective approach of solving these type of problems is map.... class Solution { public: int majorityElement(vector& nums) { map mp; for(int i=0;i n){ return itr.first ; } } return -1; } };

[@techdose4u]

Thanks for sharing

[@beep1677]

I think most ppl know this approach u should try to learn different approaches for same question than to sticking to one solution

[@peter9759]

Explained very well bro thanks for the help

[@anilchaudhry804]

This is actually called Moore's Voting Algorithm

[@techdose4u]

Yes correct

[@johnwick-gj9gb]

who give shit about Moore's "Voting" Algorithm man... we should be thankful from Tech Dose team

[@saket9363]

Cmon@@johnwick-gj9gb! We know someone killed your dog! But it was not Anil! Calm down man!

[@rajasthanikitchen2163]

@@saket9363 best reply bro

[@rahulraaghava3603]

Great explanation, Thank you

[@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

[@techdose4u]

Great ❤️

[@bjaashish]

[3,3,4] not working in this testcase

[@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]

[@techdose4u]

Thanks for sharing

[@shreyaskaup]

if you're sorting array you're not doing optimally and problem becomes too easy

[@omarkhan5223]

But then your Solution is at least n log n which isn't very impressive

[@satyamgupta6030]

very nice explaination thanks a ton.

[@abhishekghosh2316]

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]

[@techdose4u]

You have to do 2 parse to find it. So it will work for all cases. 2nd pass is verification of candidate

[@CraftMusic]

just check if the majority counter is more than n/2, then return the number.

[@alijama9221]

@@techdose4u using one loop how is it possible to make second pass? and if we use second pass, it is O(n^2)

[@saravana6882]

@@alijama9221 No not like that . before returning majority variable, run another loop and keep counting no of time actually majority element occurs in array. in simple words , the value stored in majority is actually candidate . we need to verify that actually before verifying that. # Leetcode 169 accepted solution. class Solution { public: int majorityElement(vector& nums) { int majority = nums[0]; int count = 1; for(int i =1;i

[@prithiviraj3070]

@@saravana6882 what if the majority element is distributed over the array instead of being together?

[@anushree3744]

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

[@techdose4u]

For this problem it is correct because majority element is always guaranteed here, otherwise you would have been required to verify candidate majority element.

[@gauravgupta1800]

Very well explained😊😊😊

[@premjeetprasad8676]

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

[@techdose4u]

Yea

[@fatimajaffal9843]

int majorityElement(vector& nums) { ios_base::sync_with_stdio(false); cin.tie(NULL); unordered_mapv; 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.

[@techdose4u]

Nice :)

[@nonameeee6969]

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

[@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

[@techdose4u]

👍🏼

[@athbuys3588]

thanks for a great explanation bro

[@adhirajbhadauria7521]

this algo fails if there is no majority element so your solution is incomplete sir

[@bjaashish]

[3,3,4] not working in this testcase

[@rushabhlegion2560]

I used map, is it optimal or not? Please let me know.

[@itsyash9427]

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

[@yesterdayoncemore5315]

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.

[@tringothanh8634]

You may not clear about the problem. An element is a majority one if its appearance in the array is > floor(n/2) and the majority element always exists, but 1 in your array appears 2 times (which only == 4/2). So that your array has no majority element, by btw this array won't be in the test cases since the majority element always exists

[@yesterdayoncemore5315]

@@tringothanh8634 Oh, yes, you are right. Under this assumption, this solution will give the right answer. Thank you. 😀

[@saianushachodapaneedi7504]

Thank you....#great explanation 👍

[@techdose4u]

Welcome :)

[@fahizmohd9609]

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

[@techdose4u]

That requires extra space.

[@abhinavminocha1894]

Please upload more videos on Graphs and Trees.

[@techdose4u]

Yea sure :)

[@sanjibkumargope2613]

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

[@techdose4u]

Okay sure

[@Shydc819]

Very famous question

[@vimalradadiya5929]

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

[@techdose4u]

Then on verifying stage you won't find the candidate to be majority element.

[@spetsnaz_2]

nice !!

[@uwu-dm7vb]

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

[@gudlagudla7104]

Hi brother , im just a beginner in java , what are the steps I have to follow to solve leetcode problems Plz help

[@techdose4u]

I have answered in another thread.

[@smirkedShoe]

Can you explain why this Moore algorithm actually works ?

[@techdose4u]

That is explained in another video....link in the description.

[@surajtopal9940]

wooow it is pretty simple

[@techdose4u]

Yea 😅

[@starc701]

Basically numbers are fighting with each other and similar ones are fighting wth non similar numbers . and both of them get killed. in the end only that number survive who has not fought any other number. for example 1 2 1 2 1. the last one never fought a battle so it got the victory.

[@Man_of_Culture.]

No bro if you think more deeply then u will notice that ,in case if any no. is in mojority than its count is greater than 0

[@muvvaaravindkarthik3382]

Sir I am a beginner to programming I have done the same question using unordered map and I get the correct ans But didn't understand what is auxilary space while storing elements into an unordered map Can u pls tell me what is auxilary space for storing elements into an unordered map

[@yashgoswami5374]

if majority element exist then that single element consumes atleast n/2 + 1 space in input array and rest n/2 -1 elements even if they all are distinct then in total map will have (n/2 -1 ) distinct elements + 1 majority element hence total n/2 elements can be there in worst case in map which is O(N) space complexity

[@ShreyaSingh-vr9qi]

IS this approach works even when none of the element is majority element ??

[@techdose4u]

Fir that.....after finding candidate majority element, you need to traverse the array once again to find the frequency of this cadidate majority element to confirm. I have given link to videos regarding your question. Watch it :)

[@ShreyaSingh-vr9qi]

@@techdose4u thanks brother 👍

[@avadheshsingh4255]

we can solve this problem by hashing also

[@sampath1215]

Hi can you tell me your pen tool for screen writing, your lectures are awesome

[@techdose4u]

Wacom

[@rawatgaming6065]

Bro can u tell.me what is the majority element in my example which is. Consider an array of elements 1,2,4,2,2,4,3,2,3,2,2 and plz bro give some explaination as it will be helpfull for me also

[@sakshiramsinghani5284]

In this example, 2 is the majority element. It's because over here n=11 and floor(n/2)=5, so hence we need to find an element that occurs more than 5 times. Here 2 is occurring 6 times, hence it is the majority element.

[@aviligondagowtham1153]

Sir pls tell snake and ladder approach

[@techdose4u]

That is simple only. Apply DFS/BFS. I said if I get time I will make it too 😅

[@aviligondagowtham1153]

@@techdose4u using linked list it will be good know

[@HimanshuSingh-ob9qo]

🙏👍

[@techdose4u]

👍

[@rezajafari6498]

KZbin would not be the same without Indians

[@anilchaudhry804]

Hey TechDose how can I contact you personally?

[@techdose4u]

LinkedIn.... LinkedIn handle is on channel.

[@codestorywithMIK]

🙏

[@techdose4u]

😅

[@codestorywithMIK]

@@techdose4u For this topic, this is the simplest and crisp explanation. Thanks

[@techdose4u]

Thanks for appreciation :)

[@SmartBoy-bz7ez]

Hey , this solution will be wrong for this array - 1 , 1 , 4 , 5 , 7 here your answer will return 7 but that is not correct.

[@techdose4u]

Here there is no majority element. So candidate will be picked as 7 in 1st step. In 2nd step (verification), 7 won't occur for >N/2 times. So, there is no majority element.

[@starc701]

@GURPEET your test case is wrong bro. its not according to the question.

[@chandrukumar8131]

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

[@RTX_valorant]

O(n**2) this is I guess

[@maximsNotes]

god bless

[@techdose4u]

Thanks ☺️

[@bipinsingh1490]

Bro if we take element as 2,2,1,3,2,4 then in this case it will give 4 but in real 2 is the majority element so this algo fails to give the correct ans.So why this algo we are using ???

[@gangkush1]

you are using wrong example. The problem says majority element is that which occurs "MORE THAN n/2 TIMES", but acc. to your example 2 is coming "EQUAL TO n/2 TIMES" which is actually a wrong example as per the question.

[@harshadagunjal2855]

@@gangkush1 what if example is 5,6,6,7,6,6,6,9 in this case also.. will it return 9?

[@gangkush1]

@@harshadagunjal2855 no it will return 6

[@rajeshbammidy180]

Easy Java soln using Stack:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Arrays/MajorityElement.java

[@anujvyas9493]

Python3 solution -------------------------------------------------------------------------------------------------------------------- def majorityElement(list_of_integers): majorityElement = -1 count = 0 # Iterating over the list_of_integers to find the majority element for number in list_of_integers: if majorityElement==-1: # Initial condition majorityElement = number count += 1 elif majorityElement == number: count += 1 else: if count == 1: majorityElement = number count = 1 else: count -= 1 # Here we don't cross-check the value of the obtained majority element is # greater than N/2 or not because in the question it is clearly mentioned # that array consists majority element return majorityElement if __name__ == '__main__': list_of_integers = list(map(int, input().split(' '))) element = majorityElement(list_of_integers) print('The majority element is: {}'.format(element))

[@techdose4u]

Thanks for sharing

[@anujvyas9493]

@@techdose4u Most welcome!

[@ajitpal0821]

why u dont used map and so much explaination..?? My Code:- class Solution { public: int majorityElement(vector& nums) { int n=nums.size(); mapmp; for(int i=0;in/2) val=x.first; } return val; } };

[@Shydc819]

Make video on peak element in an array

[@techdose4u]

That is very easy bro 😅

[@thewonderingworld9301]

JAVA SOLUTION*** public class Solution { public int majorityElement(int[] nums) { if (nums == null || nums.length ==0){ return 0; } int major = nums[0]; int count = 1; for(int i=1;i

[@mohammedsadiq5729]

Shit! I had used a hashmap🤦🏻‍♂️

[@techdose4u]

😅