soapyigu/LeetCode-Swift

Majority Element [Array Problem] algorithm issues.

dkeso611 opened this issue · 3 comments

dkeso611 commented

The current algorithm will always return the last integer to displace the major as the new majority element. Take var array = [1,1,1,2,2,3] for example. The answer should be 1 but the algorithm returns 3.

Also, majority element must appear more than number of elements/2 times. The algorithm doesn't take this in to account.

Thanks for all your hard work!

iHackSubhodip commented

Hi @dkeso611 ,

Here I can see the input array [1,1,1,2,2,3] is, Please find my thoughts below:

  1. number of elements = 6, so 6/2 = 3, so 1 should occur more than 3 times. so 1 is not a valid output.
    Tip - change the input to [1,1,1,1,2,2,3] -> output will come as 1 [ as 1 appeared more than 3 times.]

  2. in the question, it's mentioned "You may assume that the array is non-empty and the majority element always exist in the array". so in your above input "[1,1,1,2,2,3]" no as such majority element exists. so, it's an invalid input[For this you're getting 3 as an answer].

Given algorithm by @soapyigu , absolutely fine and works. Hope my clarification clears your doubt.

Best Regards!

dkeso611 commented

You're right. Thanks for taking the time out to answer my questions!

  • 👍1
iHackSubhodip commented

@dkeso611 , no problem! I am glad my answer cleared your doubt :)