Introduction
In this tutorial, we’ll explore the “Majority Element” interview question and provide a comprehensive solution using C++. The Majority Element is a common coding interview problem that tests your ability to find an element that appears more than n/2 times in an array of size n. We’ll walk through the problem statement, discuss different approaches to solving it, and implement the solution in C++.
Problem Statement
You are given an array of integers, and you need to find the majority element. A majority element is an element that appears more than n/2 times in the array, where n is the size of the array. It is guaranteed that a majority element always exists in the array.
For example, consider the array:
[3, 1, 3, 3, 2]
In this case, the majority element is 3, as it appears three times, which is more than half of the total elements (5/2 = 2.5).
Brute Force Approach
A straightforward approach to solving this problem is by using nested loops to count the occurrences of each element and finding the one that appears more than n/2 times. Here’s a step-by-step breakdown of this approach:
- Initialize a variable
maxCount
to keep track of the maximum count of an element. - Initialize a variable
majorityElement
to store the element that appears more than n/2 times. - Loop through each element
num
in the array.
- Initialize a variable
count
to 0. - Loop through the array again to count the occurrences of
num
. - If
count
is greater thanmaxCount
, updatemaxCount
andmajorityElement
.
- After both loops,
majorityElement
will contain the majority element.
Implementation
Here’s the implementation of the brute force approach in C++:
#include <iostream>
#include <vector>
int findMajorityElement(const std::vector<int>& nums) {
int n = nums.size();
int maxCount = 0;
int majorityElement = 0;
for (int num : nums) {
int count = 0;
for (int otherNum : nums) {
if (otherNum == num) {
count++;
}
}
if (count > maxCount) {
maxCount = count;
majorityElement = num;
}
}
return majorityElement;
}
int main() {
std::vector<int> nums = {3, 1, 3, 3, 2};
int majority = findMajorityElement(nums);
std::cout << "Majority Element: " << majority << std::endl;
return 0;
}
Optimal Approach: Boyer-Moore Voting Algorithm
The brute force approach works, but it has a time complexity of O(n^2) due to the nested loops. We can achieve a more efficient solution using the Boyer-Moore Voting Algorithm, which has a time complexity of O(n) and a space complexity of O(1).
The key idea behind this algorithm is that if we cancel out each occurrence of an element x
with all the other elements that are different from x
, then x
will be the majority element if it indeed is a majority element.
Here’s a step-by-step breakdown of the Boyer-Moore Voting Algorithm:
- Initialize two variables
candidate
andcount
to keep track of the current candidate for the majority element and its count, respectively. - Loop through each element
num
in the array.
- If
count
is 0, assignnum
tocandidate
and setcount
to 1. - If
num
is the same ascandidate
, incrementcount
; otherwise, decrementcount
.
- After the loop, the
candidate
will contain the majority element. - To confirm that the
candidate
is the majority element, loop through the array again and count its occurrences.
- If the count of
candidate
is greater than n/2, returncandidate
; otherwise, return -1 to indicate no majority element.
Implementation
Here’s the implementation of the Boyer-Moore Voting Algorithm in C++:
#include <iostream>
#include <vector>
int findMajorityElement(const std::vector<int>& nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
// Confirm the candidate is the majority element
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
if (count > nums.size() / 2) {
return candidate;
} else {
return -1; // No majority element
}
}
int main() {
std::vector<int> nums = {3, 1, 3, 3, 2};
int majority = findMajorityElement(nums);
if (majority != -1) {
std::cout << "Majority Element: " << majority << std::endl;
} else {
std::cout << "No Majority Element" << std::endl;
}
return 0;
}
Testing and Analysis
Let’s test our solution with various inputs to ensure its correctness and efficiency.
Test Case 1
Input:
[3, 1, 3, 3, 2]
Output:
Majority Element: 3
Test Case 2
Input:
[1, 2, 2, 3, 2]
Output:
Majority Element: 2
Test Case 3
Input:
[1, 2, 3, 4, 5]
Output:
No Majority Element
Conclusion
In this tutorial, we’ve covered the Majority Element interview question and provided a detailed solution in C++. We discussed both the brute force approach and the more efficient Boyer-Moore Voting Algorithm. By using the Boyer-Moore algorithm, we can solve the problem in O(n) time complexity and O(1) space complexity, making it a much more efficient solution. Remember to thoroughly test your code with different test cases to ensure its correctness and efficiency in various scenarios. Happy coding!