Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Majority Element (Main Thread)

Here is the interview question prompt, presented for reference.

Suppose we're given an array of numbers like the following:

[4, 2, 4]

Could you find the majority element? A majority is defined as "the greater part, or more than half, of the total. It is a subset of a set consisting of more than half of the set's elements."

Let's assume that the array length is always at least one, and that there's always a majority element.

In the example above, the majority element would be 4.

Constraints

  • Length of the array <= 100000
  • The array will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked almost 2 years ago by Anonymous

Jake from AlgoDaily Commented on Aug 07, 2019:

This is the main discussion thread generated for Majority Element.

Anonymous Commented on Aug 07, 2019:

If the solution is:

function majorityElement(nums) {
var major = Math.floor(nums.sort().length / 2);
return nums[major];
}

Why does nums = [1, 2, 2, 2, 3, 4, 4, 4, 4] return 3 when 4 is still the majority?

Jake from AlgoDaily Commented on Aug 08, 2019:

Hi,

In your example, there is no majority element. A majority is defined as "the greater part, or more than half" of the total. Remember we're talking about majority, not mode. To be the majority, there would need to be at least 5 out of 9.

Anonymous Commented on Aug 28, 2019:

The solution is wrong. It fails on the following

majorityElement([4, 2, 4, 9, 9900, 990, 909, 200, 100, 904, 900, 1])

Anonymous Commented on Aug 28, 2019:

Nevermind I confused this with 'mode'

Commented on Sep 02, 2019:

My brute force approach gave a linear solution:

def majority_element(nums):
f = {}
m = len(nums)
for n in nums:
if not (n in f):
f[n] = 0
f[n] += 1
if f[n] * 2 > m:
return n
return None

Anonymous Commented on Sep 17, 2019:

kl=[4, 2, 4, 9, 9900, 990, 909, 200, 100, 904, 900, 1]
from collections import Counter
n=Counter(kl)
vl=list(n.values())
vlm=vl.index(max(vl))
kl=list(n.keys())
result=kl[vlm]
print(result)

Anonymous Commented on Sep 17, 2019:

kl=[4, 2, 4, 9, 9900, 990, 909, 200, 100, 904, 900, 1]
from collections import Counter
n=Counter(kl)
vl=list(n.values())
vlm=vl.index(max(vl))
kl=list(n.keys())
result=kl[vlm]
print(result)

Anonymous Commented on Dec 08, 2019:

"if not (n in f):" has a complexity of O(m);
where m = no of elements in f

This is because to check for n in f, there is an iteration through the set f.

Hence the time complexity of this code is O(nm)

Commented on Dec 10, 2019:

This is because to check for n in f, there is an iteration through the set f.

Who told you that? Operator in invokes f.__contains__(x) which is O(1) for a hash set. See https://docs.python.org/3.7/reference/expressions.html#in

Anonymous Commented on Jan 04, 2020:

I felt like I cheated when doing this but here it is:

def majority_element(nums):
i = 0
co =[]
for ele in nums:
co1 = nums.count(nums[i])
co.append([co1,nums[i]])
i = i+1
return max(co)[1]

Anonymous Commented on Aug 19, 2020:

The phrasing was a little confusing for what was meant by "majority element", until I rephrased in my head as meaning: value with >= 50% of "occurrences". Not sure if this is just me :)

Anonymous Commented on Oct 18, 2020:

An alternative solution is Boyer-Moore voting with time complexity is O(n), space complexity is O(1)
The implementation in Scala is:

def mooreVoting(xs: Array[Int]): Int = {
  if (xs.length == 1) xs(0)
  else {
    var count = 0
    var candidate = Integer.MIN_VALUE // or null value

    for (x <- xs) {
      if (count == 0) candidate = x

      val vote = if (x == candidate) 1 else -1
      count += vote
    }

    candidate
  }
}
ychennay Commented on Dec 29, 2020:

Why is iterating through the list O(N2) complexity as it says in the list? You store all the counts in a hash table with O(1) lookup, and you stop whenever a count >= n / 2? I don't see where the N2 is coming from?

Jake from AlgoDaily Commented on Dec 29, 2020:

Hey ychennay,

Are you referring to the AlgoDaily tutorial? If so, the O(N^2) complexity was referring to the brute force solution, where we pass the list and then at each element, go through another list. - "This is an O(n2) solution because it would require passing through each number, and then at each number scanning for a count."

The final solution is O(n * log n) since we sort it.

Edit: disregard, just saw your mention of a hash-- maybe referring to a solution higher up in this thread.

ychennay Commented on Dec 29, 2020:

Jake - yes, I'm referring to the AlgoDaily tutorial. I guess I'm confused because I don't see why we need to sort first (which introduces the O(n * log n)).

Couldn't you iterate through the unsorted list, maintaining a dictionary in Python of counts using collections.Counter, and then whenever the current element's count is >= n // 2, you return that element?

The worst case scenario there would be O(N), having to iterate through the entire list, and look up the count for each element (which should be O(1) lookup)?

Jake from AlgoDaily Commented on Dec 29, 2020:

Yep, that's certainly another way to do it. The trade-off is that you'd need to allocate extra space (proportional to the input array) specifically for the hash map.

You bring up a good point though-- I'll be sure to address the O(n) solution in the tutorial.

Ahmed Magdy Seleem Commented on Jan 11, 2021:

Hi,

in the final solution I don't understand it for these reasons:

1- How sort method works this way ?
it sorts array according to numbers or UTF code, not sort by majority numbers

2- What if there is No Majority Number ?
the function always return a number

Jimmy Shephard Commented on Mar 30, 2021:

I have the same concerns as Ahmed, how is this solution correct if it always returns a value even when there's clearly not a majority in the array??

ran Commented on May 25, 2021:

Hello,

I agree with Ahmed and Jimmy above me, in regards to the Final Solution using the .sort() and Math.floor() methods in JavaScript.

Ran a test with an array of numbers:
let numSample = [5,5,5,4,2,3,4]; // returns 4

And, still received a number back even though it does not fit the criteria for a majority element. A conditional would have to be written into the function to account for this.

Jitin Commented on Jun 10, 2021:

One of the assumptions in the problem is that there is always a majority element in the array, hence the above input could be considered as invalid