(Remade) Leetcode 169 - Divide And Conquer | Majority Element

Topic: Divide And Conquer

Code:

Leetcode:

*Note* I claim no rights to this question. All rights belong to Leetcode. If I'm reviewing a solution that was from another Leetcode user or Leetcode itself I will give credit below.

Intro:(0:00)
I/O:(0:12)
Approach:(1:58)
Code:(3:36)
Complexity:(4:32)

Hey there! Just wanted to let you know that some of the links in this video description are affiliate links, which means that if you make a purchase through them, I may earn a small commission. Don't worry though, it doesn't cost you anything extra and it helps support this channel so I can continue to make more videos for you. Thank you so much for your support, and as always, all opinions are my own!

[ah-rdk]

That Was the Exact Divide and Conquer Algorithm I Was Looking for.
Well Explained! Thank You.

[topG]

I have been following you for a while but what I found exceptional about you is your solutions are typically what interviewers are looking for. It is tempting to use hashtable for a question like this however because of how obvious that is most interviewers would expect something different

[NideeshTerapalli]

Hey there! Just wanted to let you know that some of the links in this comment are affiliate links, which means that if you make a purchase through them, I may earn a small commission. Don't worry though, it doesn't cost you anything extra and it helps support this channel so I can continue to make more videos for you. Thank you so much for your support, and as always, all opinions are my own!

[ganeshkumar-yezq]

what should we do when left != right and left subarray count == right subarray count.

[mohdnavedkhan]

It was explained amazingly
Thanks bro!

[vladflorea]

Very good explanation. Thanks man, subscribed!

[wenjieyu]

Thank you for explanation! It helps me a lot.

[sujangyawali]

What if left part don't have majority element?

[MrTolmachina]

What happens in case left = 2, 2 right =3, 3 ?

[pratyushsingh]

Thanks a lot for explaining this problem.

[shaggypeach]

Still not getting it. Been on this problem for days now. I wrote this in python and I get index out of bound.

[seal]

it was really simple, i completely understand how it works, thanks a lot but i just have 2 questions
is there proof that this algorithm actually works for all cases (when a majority element is guaranteed)?

3:37 i have seen code where its slightly different where the counter function starts counting from i to j (from start to end) independent of the mid point of the array, isn't that considered bad practice and you would actually do more work that way?

[sujangyawali]

For eg: right half is 3, 4. Here, 3, 4 is divided till base case. Subleft 3 return 3 as max and Subright 4 return 4 as max. Since result was different. We have to run loop to check count countSublefthalf greater return subleft 3 otherwise subright 4. But one thing i didn't get is while iterating in count method we are taking range of only lefthalf instead of entire array. What we are trying to do by seeing occurence in left half array only. In this case to see occurence of 3 in count method we are iterating from 0 to 0 ???😂😂😂

[harrypounds]

WHy is it not T(n) =2T(n/2)+2n. and not T(n) =2T(n/2)+n. thanks for vid

[srivaishnav]

Using Moores voting algorithm we can we can further optimize it to n.

[harriskhawar]

this method doesn't work for all cases... suppose you have array [1, 3, 1, 2]. since the count comparison statement will return right even when left and right count are same, you will get the result 2, which wrong.
Considering the recency of this video, please at least mention this problem so as to not misguide any viewers.