1. Introduction
In this tutorial, we’ll explore different approaches to finding the majority element within an array. For each approach, we’ll provide their respective code implementations and analysis of time and space complexities.
2. Problem Statement
Let’s understand the problem of finding the majority element in an array. We’re given an array of integers and our objective is to determine if a majority element exists within it.
A majority element appears more frequently than any other element, surpassing the threshold of occurring more than n/2 times in the array, where n represents the array’s length. This means identifying the element that dominates the array in terms of occurrence frequency.
Before delving into each approach, we’ll utilize the provided sample data as input:
int[] nums = {2, 3, 2, 4, 2, 5, 2};
3. Using a for Loop
One straightforward approach to finding the majority element involves iterating through the array with a for loop. This approach involves iterating through the array using a for loop and maintaining a count of occurrences for each element. We’ll then check if any element satisfies the majority condition, meaning it appears in more than half the slots of the array.
3.1. Implementation
In this implementation, we iterate through the array using a for loop. For each element in the array, we initialize a count variable to keep track of its occurrences. Subsequently, we iterate through the array again to count the occurrences of the current element.
As we iterate through the array, if we encounter a majority element with a count greater than n/2, we can immediately return the element:
int majorityThreshold = nums.length / 2;
Integer majorityElement = null;
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
if (count > majorityThreshold) {
majorityElement = nums[i];
break;
}
}
assertEquals(2, majorityElement);
3.2. Complexity Analysis
The time complexity of the for-loop approach is O(n^2). This quadratic time complexity arises due to the nested loops utilized in the implementation, where each element in the array is compared against every other element. On the other hand, the space complexity is O(1).
While the approach is simple to implement and has minimal space overhead, it’s not the most efficient for large arrays due to its quadratic time complexity.
4. Using a Sorting Approach
In this approach, we leverage a sorting algorithm to efficiently identify the majority element in an array. The strategy involves sorting the array in ascending order, which enables us to identify consecutive occurrences of elements.
Given that a majority element appears more than half the size of the array, after sorting, it will either occupy the middle index (if the array length is odd) or be next adjacent to the middle elements (if the array length is even). Consequently, by examining the middle elements of the sorted array, we can ascertain whether one of them qualifies as the majority element.
4.1. Implementation
First, we use Arrays.sort() to sort the array in ascending order. This step is crucial as it enables us to identify consecutive occurrences of elements more easily. Next, we iterate through the sorted array and keep track of the middle element’s occurrence count. Inside the loop, we also check if the count is greater than half the size of the array.
If it is, it means the current element has appeared more than half the time, and it’s identified as the majority element. The code then returns this element. Let’s demonstrate this concept using a code snippet:
Arrays.sort(nums);
int majorityThreshold = nums.length / 2;
int count = 0;
Integer majorityElement = null;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == nums[majorityThreshold]) {
count++;
}
if (count > majorityThreshold) {
majorityElement = nums[majorityThreshold];
break;
}
}
assertEquals(2, majorityElement);
4.2. Complexity Analysis
The time complexity of this approach is typically O(n log n) due to sorting, and the space complexity is O(1) as it uses constant extra space. This approach is slightly more efficient compared to the for-loop approach, but it might not be the most optimal solution for very large arrays due to the sorting operation’s time.
5. Using HashMap
This approach uses a HashMap to store the frequency of each element in the array.
5.1. Implementation
In this approach, we iterate through the array, incrementing the count of each element we encounter in the HashMap. Finally, we iterate through the HashMap and check if any element’s count is greater than half the size of the array. If a majority element is found, we return it; otherwise, we return -1 to indicate that no majority element exists in the array.
Here’s an example implementation:
Map<Integer, Integer> frequencyMap = new HashMap<>();
Integer majorityElement = null;
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int majorityThreshold = nums.length / 2;
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() > majorityThreshold) {
majorityElement = entry.getKey();
break;
}
}
assertEquals(2, majorityElement);
5.2. Complexity Analysis
Overall, using a HashMap is a more efficient approach, especially for larger datasets, due to its linear time complexity. It has a time complexity of O(n) due to iterating through the array once and iterating through the HashMap once.
However, this approach requires additional space for HashMap, which can be a concern for memory-constrained environments. In the worst-case scenario, the space complexity will be O(n) as the HashMap might store all unique elements in the array.
6. Using the Boyer-Moore Voting Algorithm
This algorithm is popularly used to find the majority element in a sequence of elements using linear time complexity and a fixed amount of memory.
6.1. Implementation
In the initialization step, we create two variables: a candidate element and a count. The candidate element is set to the first element in the array, and the count is set to 1.
Next, in the iteration step, we loop through the remaining elements in the array. For each subsequent element, we increment the count if the current element is the same as the candidate element. This signifies that this element also potentially contributes to being the majority. Otherwise, we decrease the count. This counteracts the previous votes for the candidate.
If the count reaches 0, the candidate element is reset to the current element, and the count is set back to 1. This is because if previous elements cancel each other out, the current element might be a new contender for the majority.
After iterating through the entire array, we verify by iterating through the array again and counting the occurrences of the candidate element. If the candidate appears more than n/2 times, we return it as the majority element. Otherwise, we return -1.
Let’s proceed with the implementation:
int majorityThreshold = nums.length / 2;
int candidate = nums[0];
int count = 1;
int majorityElement = -1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (candidate == nums[i]) {
count++;
} else {
count--;
}
}
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
majorityElement = count > majorityThreshold ? candidate : -1;
assertEquals(2, majorityElement);
Here is the breakdown of the iteration step:
Initial stage: [Candidate (2), Count (1)]
Iteration 1: [Candidate (2), Count (0), Element (3)] // "3" != candidate, count--
Iteration 2: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
Iteration 3: [Candidate (2), Count (0), Element (4)] // "4" != candidate, count--
Iteration 4: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
Iteration 5: [Candidate (2), Count (0), Element (5)] // "5" != candidate, count--
Iteration 6: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
6.2. Complexity Analysis
*This algorithm has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for finding the majority element in an array.*
7. Summary
This table summarizes the time and space complexities of each approach as well as their advantages. It provides a quick overview of the trade-offs and benefits of each approach.
Approach
Time Complexity
Space Complexity
Pros & Cons
For loop
O(n^2)
O(1)
– Straightforward to implement
– Requires minimal additional space
– Inefficient for large arrays due to nested loops
Sorting
O(n log n)
O(1) or O(n)
– Simple implementation
– No additional space overhead if in-place sorting is used
– Introduces additional time complexity due to sorting
HashMap
O(n)
O(n)
– Linear time complexity for both processing and space usage
– Efficiently handles large arrays
– Requires additional space for HashMap storage
Boyer-Moore Voting
O(n)
O(1)
– Optimal time and space complexity
– Efficient for large arrays
8. Conclusion
In this article, we explored various approaches to finding the majority element in an array.
The for-loop approach provides a simple implementation but is inefficient for large arrays due to its nested loops. The HashMap approach provides linear time complexity and efficiently handles large arrays, but it requires additional space for HashMap storage.
Finally, the Boyer-Moore Voting Algorithm offers optimal time and space complexity and is efficient for large arrays.
As always, the source code for the examples is available over on GitHub.