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.
1function majorityElement(nums) {
2 const counts = {};
3 for (const num of nums) {
4 counts[num] = counts[num] ? counts[num] + 1 : 1;
5 }
6 const majorityCount = Math.floor(nums.length / 2);
7 for (const num in counts) {
8 if (counts[num] > majorityCount) {
9 return parseInt(num);
10 }
11 }
12 return -1; // Unreachable in problem's context
13}
14
15console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));JavaScript also manages counts via an object hash map, allowing dynamic key-value handling. After counting, keys are checked for the count exceeding half the array length.
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
Python's implementation is concise, leveraging the same increment and decrement pattern that characterizes the Boyer-Moore algorithm.