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`

.

- 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

This is the main discussion thread generated for Majority Element.

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?

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.

The solution is wrong. It fails on the following

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

Nevermind I confused this with 'mode'

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

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)

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)

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

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

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]

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

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
}
}
```

Why is iterating through the list O(N^{2)} 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^{2} 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^{2)} 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