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.
1import java.util.HashMap;
2import java.util.Map;
3
4public class MajorityElement {
5 public static int majorityElement(int[] nums) {
6 Map<Integer, Integer> countMap = new HashMap<>();
7 for (int num : nums) {
8 countMap.put(num, countMap.getOrDefault(num, 0) + 1);
9 }
10 int majorityCount = nums.length / 2;
11 for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
12 if (entry.getValue() > majorityCount) {
13 return entry.getKey();
14 }
15 }
16 return -1; // Unreachable code due to problem assumptions
17 }
18
19 public static void main(String[] args) {
20 int[] nums = {2, 2, 1, 1, 1, 2, 2};
21 System.out.println(majorityElement(nums));
22 }
23}Java’s HashMap API is used similarly to maintain the count of each number. A loop then goes through these entries to find the majority element.
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.