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
class MajorityElementSolver {
public static int MajorityElement(int[] nums) {
int count = 0, candidate = 0;
foreach (int num in nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
static void Main() {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
Console.WriteLine(MajorityElement(nums));
}
}C# uses the Boyer-Moore algorithm to simplify the operation of ensuring majority element finding in a controlled pass through the array.