This is the main discussion thread generated for Majority Element.

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.

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


> 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

Why is iterating through the list O(N²⁾ 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 N² is coming from?

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(n²⁾ 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.

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

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.

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

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

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.

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

Solution shows different result based on the majority defenition.

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

console.log(majorityElement([1, 4, 4, 2, 2, 2, 2, 4, 4, 3, 4]));

returns 3 when there is no majority as per the defenition and response to a previous answer?

Hey Sareesh,

Part of the problem is Let's assume ... that there's always a majority element, so the expectation is that there is a majority. Let me know if that makes sense.

My solution (which takes into account that there may not be a majority) is:

function majorityElement(nums) {
    nums.sort();
  let majorityCandidate = nums[Math.floor(nums.length /2)];
  const frequency = nums.filter((num) => num === majorityCandidate);
  if ( frequency.length >= (nums.length / 2)) {
    return majorityCandidate;
  }
  return [];
}

I'm still not 100% sure about time & space complexity - would appreciate if someone could explain whether the above is a good solution in view of that.