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

Topic: Divide And Conquer
Code:
github.com/Nideesh1/Algo/blob...
Leetcode:
leetcode.com/problems/majorit...
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.
Credit to : Leetcode Solution (leetcode.com/problems/majorit...)
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!
Start getting great at system design: bytebytego.com?fpr=nideesh (affiliate link)
Handpicked Algorithms and Data Structures for Interview To Save Time: interviewpen.com/?via=nideesh
Fast track to becoming a knowledgeable SWE www.educative.io/unlimited?af... (affiliate link)

[@amirhossein.roodaki]

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

[@kunjmaheshwari9819]

nice explanation. Thankyou!

[@topG448]

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

[@wenjieyu6242]

Thank you for explanation! It helps me a lot.

[@vladflorea7048]

Very good explanation. Thanks man, subscribed!

[@mohdnavedkhan5265]

It was explained amazingly Thanks bro!

[@MustafaYasarr]

Comprehensible explanation. Thanks

[@pratyushsingh2809]

Thanks a lot for explaining this problem.

[@ganeshkumar-ye4zq]

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

[@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! Start getting great at system design: bytebytego.com?fpr=nideesh (affiliate link) Handpicked Algorithms and Data Structures for Interview To Save Time: interviewpen.com/?via=nideesh Fast track to becoming a knowledgeable SWE www.educative.io/unlimited?aff=K1z6 (affiliate link)

[@bhavyabhargava3700]

Great explanation bro!!! 👍

[@hadiyouness5449]

Great Explanation

[@sameerasuhail2158]

Thank you!

[@sujangyawali418]

What if left part don't have majority element?

[@shaggypeach]

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

[@MrTolmachina]

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

[@tanaykamath1415]

that means there is no majority element as floor(n/2)=2 and no element appears more than 2 times, but is an issue if it appears as a subarray during the computation!!, thus his divide and conquer approach might fail The most appropriate way to solve this is by Moore's voting algo. in O(n) time

[@sujangyawali418]

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 ???😂😂😂

[@seal0118]

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?

[@RubLox_Live]

its not necessary to have i and j but just an input of array. I think its just for explaining purposes. We dont need two functions, 1 will suffice

[@harrypounds456]

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

[@srivaishnav2319]

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

[@steveochoa7801]

The point is to use a D&Q approach

[@harriskhawar7901]

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.

[@harriskhawar7901]

Also you should use i and j as starting and ending points for counting both left and right instead of i and m for left and m+1 and j for right.

[@NideeshTerapalli]

@@harriskhawar7901 Read the problem description. The leetcode question guarantees that The majority element is the element that appears more than ⌊ n/2 ⌋ times. Your example is invalid input

[@ermannoserrati5088]

@@NideeshTerapalli Hi, thanks for video and the good explanation. Suppose that you have to manage the case on which the input has not majority element and to tell this on output (for example using a negative number), it is possibile adapt the solution that you provide?

[@luxcide]

@@NideeshTerapalli how about for array [3 3 2 2 3] , the left and right count of 3 and 2 will both be two

[@steveochoa7801]

@@luxcide that's not true - when the recursive calls are all popped off the stack and the values returned to the initial call - then we will see that left majority value = 3 and right majority value = 3 (or it could be 2, but either way the count() helper will be called and it will result in the correct value of 3 as the overall majority value)