Majority Element - Solution
Solutions and explanations
- Sort the array.
- The middle element is guaranteed to be the majority element because:
- As per the constraints, the majority element always exists in the array.
- It appears more than
⌊n / 2⌋times, wherenis the array size.
Since it occurs more than half the time, it must occupy the middle position after sorting.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
Complexity Analysis
Here, n is the size of the input.
- Time Complexity:
O(n log n) - Space Complexity:
O(1)orO(n)depending on the implementation of sorting algorithm.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
freq_map = collections.defaultdict(int)
majority_element, highest_count = 0, 0
for num in nums:
freq_map[num] += 1
if freq_map[num] > highest_count:
majority_element = num
highest_count = freq_map[num]
return majority_element
Complexity Analysis
Here, n is the size of the input.
- Time Complexity:
O(n) - Space Complexity:
O(n)
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count_map = Counter(nums)
most_common_list = count_map.most_common(1)
return most_common_list[0][0]
Complexity Analysis
Here, n is the size of the input.
- Time Complexity:
O(n) - Space Complexity:
O(n)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cur_majority_ele, count = None, 0
for num in nums:
if count == 0:
cur_majority_ele, count = num, 1
elif cur_majority_ele == num:
count += 1
else:
count -= 1
return cur_majority_ele
Complexity Analysis
Here, n is the size of the input.
- Time Complexity:
O(n) - Space Complexity:
O(1)