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
.
100000
-2147483648
and 214748364
O(n)
O(n)
You can see the full challenge with visuals at this link.
Challenges • Asked over 1 year ago by Anonymous
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?
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.
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)
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)
"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(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?
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.
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