I HATE This Coding Question, but FAANG Loves it! | Majority Element - Leetcode 169

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[mujtabarehman]

It’s called the Boyer-Moore Majority vote algorithm. Not to be confused with Boyer-Moore string matching. Looks like Boyer and Moore were just really good at inventing new algorithms together

[WoWUndad]

Memorizing leetcode tricks is the dumbest software engineering test i could think of in 2024

[abdulamite]

Boyer-Moore voting is so clean and simple and doesn’t need the same space as a hash map

[kefpull]

If it's making you confused, you should rename the "count" to "balance", which is how it is normally depicted in Boyer - Moore voting. I hope this helps!

[williamable]

I’ll file this under “shit I will never, ever need to know as a programmer”

[connorskudlarek]

The reeeally important part was "in over half". If that part isn't stated, this solution won't work.

[lillii]

Me a mathematician:
"Ok but now prove it works"

[skeltek]

[1, 1, 1, 2, 3, 4, 4] results in 4.
The solution is stupid, since determining the requirement of knowing a 'candidate' representing more than 50% of the elements being true, usually requires more calculating power than solving the initial problem.

[tekno]

the fact that you’re just supposed to somehow know this is ridiculous. no one is coming up with this on the spot unless they’ve already seen it

[ericb]

I came up with an analogy for this problem that helped me understand why this works. It's like a tug of war. To take a simple case, imagine there are only two distinct numbers in the array and one has the majority. Now visualise a point on a number line, starting at 0. Each occurence of one number "tugs" the point towards one side, while the other "tugs" towards the other side with equal force/step count. As you count through the array, no matter which order they are in, the point will end up on the side of the majority.

[EricKing]

This is not a coding question, it's an algorithm trivia question

[reynoldskynaston]

This only works if there are only 2 values in the array

[vsnyk]

Why is it O(1) and not O(n) as you loop through the array once. Can you explain please?

[Melliniumorder]

It sucks as a question because theres basically only one correct answer to make it O(1), and the conditions are contrived to make it such, so you have to memorise the right solution that people wrote a paper to explain.

[Phenom]

As someone who write scripts in python for automation in my IT job and has a degree in CS I sometimes for get about time complexity. Here is what I have for the question:
def majority(lst):
# Turning list values into keys for dictionary
# Setting Values to 0
tmp = dict.fromkeys(lst, 0)

# Loop Through and counts occurences of Keys
for k, v in tmp.items():
for i in lst:
if k == i:
tmp[k] += 1
# Returning Key with Max Value
return(max(tmp, key=tmp.get))

[FlashKillerX]

These shorts are just reinforcing how happy I am with my decision to get out of programming and into data

[sebastiangudino]

With these kind of questions i always imagine me turning a pretty similar answer in. And being told "Actually, there is this very obscute unproven theorem from nunber theory that says if you sum the array and take the floor of the pi base log of the sum you get the answer in constant time"

[ImaginaryMdA]

I feel like this requires a non trivial proof of correctness.

[yujiruffhanma]

One question: how is this constant time? You still have to make a full pass along the length of the array, which takes longer if the array is longer.