Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Majority Element - Python - Description Question

Challenges • Asked over 3 years ago by abrar

abrar Commented on Aug 05, 2020:

the solution mentinons sorting (O(nlogn)).
instead we can use dictionary/hashmap
sorting in O(n), n = number of elements
searching for majority element O(m) at worst case, m = number of keys of dictionary
where m < n

overall we are doing it in O(n), linear time

`def majorityelement(nums):
n = len(nums)/2
count
dict = {}

# set item count to dict
for item in nums:
countdict[item] = countdict.get(item, 0) + 1

# count the number of occurances
for key in countdict.keys():
if count
dict[key] > n:
return key`

Link to problem: Majority Element.