Sponsored
Sponsored
This approach involves counting the frequency of each element using a HashMap (or a Dictionary). We store each element as a key and maintain its count as the value. Finally, we determine which key has a count greater than half the length of the array.
Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store counts.
1def majorityElement(nums):
2 counts = {}
3 for num in nums:
4 if num in counts:
5 counts[num] += 1
6 else:
7 counts[num] = 1
8 for num, count in counts.items():
9 if count > len(nums) // 2:
10 return num
11
12print(majorityElement([2, 2, 1, 1, 1, 2, 2]))Python utilizes a dictionary for counting, and then iterates through the dictionary to retrieve the majority element by scanning through its counts.
The Boyer-Moore Voting Algorithm is an efficient solution that processes the array in a single pass. It maintains a count for the majority candidate. At the end of the loop, since the majority element exists, the candidate will be the majority element.
Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables.
1
Boyer-Moore works by selecting a potential candidate and adjusting a counter up and down as it processes the list. If the counter becomes zero, a new candidate is considered. The majority presence guarantees the candidate is correct.