Majority Element Validator — Problem Statement & Solution Guide
Problem Description
You are provided with an integer array nums of length n. Your task is to determine whether a majority element exists in the array. A majority element is defined as any value that appears strictly more than n/2 times. If such an element exists, return it; otherwise, return -1.
The problem requires an efficient solution that avoids using extra space for frequency counting. You must leverage the properties of the array to identify the candidate in linear time with constant space complexity.
Input: An array nums of integers.
Output: The integer value that constitutes the majority element, or -1 if no such element exists.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Majority Element Validator"
WHY DOES IT MATTER?
The voting pattern exemplifies how to reduce auxiliary storage by exploiting problem‑specific invariants, a skill crucial for designing scalable algorithms in memory‑limited contexts.
OPTIMIZATION CHALLENGE
The key insight is that pairs of differing elements can be discarded without affecting the majority outcome, turning a counting problem into a simple linear scan with a constant‑size state.
REAL-WORLD CONNECTION
Think of a distributed consensus where nodes vote for a leader; minority votes cancel each other out, and only a leader with >50% support survives—mirroring the cancellation process of Boyer‑Moore.
In an interview, write the voting loop first, then immediately add the verification pass; this shows you understand both the algorithmic guarantee and its practical correctness check.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The majority‑element problem can be solved in linear time with constant extra space using the Boyer‑Moore Voting Algorithm. The algorithm maintains a candidate and a counter; when the current element matches the candidate the counter is incremented, otherwise it is decremented. If the counter drops to zero, the next element becomes the new candidate. This works because any element that is not the majority can cancel out at most an equal number of majority occurrences, guaranteeing that a true majority survives to the end.
A naive frequency map (hash table) also runs in O(n) time but consumes O(n) additional space, which becomes prohibitive for very large inputs or memory‑constrained environments. Sorting the array yields a majority at the middle index, but sorting costs O(n log n) time and modifies the input. The Boyer‑Moore approach sidesteps both issues by leveraging the cancellation property of pairs of different elements, achieving the optimal O(n) time and O(1) space bound.
After the first pass we obtain a candidate that *might* be the majority. A second linear pass is required to verify that the candidate actually appears more than n/2 times, because the algorithm only guarantees that a majority will survive, not that a survivor is necessarily a majority when none exists.
Interview Questions on This Problem
Q1Explain how the Boyer‑Moore Voting Algorithm finds a majority element in O(n) time and O(1) space.
It iterates once, keeping a candidate and a count. When the current number equals the candidate, count++. Otherwise count--. If count reaches zero, the next number becomes the new candidate. After the pass, the candidate is verified with a second pass to ensure it appears > n/2 times.
Q2Why must we perform a second pass after the voting phase?
The voting phase only guarantees that a true majority cannot be eliminated; if no majority exists, the algorithm still returns a candidate. The second pass counts the candidate's occurrences to confirm it exceeds n/2, otherwise we return -1.
Q3How would you adapt the algorithm to find an element that appears more than ⌊n/3⌋ times?
Use the extended Boyer‑Moore approach that tracks up to two candidates and their counts, because at most two numbers can appear > n/3 times. After the first pass, verify both candidates with a second pass.
Examples
Input
nums = [3, 3, 4, 2, 3, 3, 1]
Output
3
Explanation: The array length is 7. The threshold for a majority is > 7/2 = 3.5, so the count must be at least 4. The element 3 appears 4 times. Since 4 > 3.5, 3 is the majority element.
Input
nums = [1, 2, 3, 4, 5]
Output
-1
Explanation: The array length is 5. The threshold is > 2.5, so the count must be at least 3. Each element appears exactly once. No element meets the threshold, so return -1.
Input
nums = [7, 7, 7, 2, 2, 2, 7, 7]
Output
7
Explanation: The array length is 8. The threshold is > 4, so the count must be at least 5. The element 7 appears 5 times. Since 5 > 4, 7 is the majority element.
Input
nums = [10, 20, 10, 30, 10, 40, 10]
Output
10
Explanation: The array length is 7. The threshold is > 3.5, so the count must be at least 4. The element 10 appears 4 times. Since 4 > 3.5, 10 is the majority element.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The array is guaranteed to be non-empty.
Optimal Approach & Strategy
Apply the Boyer‑Moore Voting Algorithm to obtain a candidate in one linear pass with constant space, then verify the candidate in a second linear pass. This yields O(n) time and O(1) space.
Brute Force Approach
Count the frequency of each element using a hash map and then scan the map for a value > n/2. This uses O(n) extra space. Alternatively, sort the array and check the middle element, which costs O(n log n) time.
Verified Code Solutions
function majorityElement(nums) {
let count = 0;
let candidate = null;
for (let num of nums) {
if (count === 0) {
candidate = num;
count = 1;
} else if (candidate === num) {
count++;
} else {
count--;
}
}
return nums.filter(x => x === candidate).length > nums.length / 2;
}class Solution {
public:
bool majorityElement(vector<int>& nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (candidate == num) {
count++;
} else {
count--;
}
}
int occurrences = 0;
for (int num : nums) {
if (num == candidate) {
occurrences++;
}
}
return occurrences > nums.size() / 2;
}
};class Solution {
public boolean majorityElement(int[] nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (candidate == num) {
count++;
} else {
count--;
}
}
int occurrences = 0;
for (int num : nums) {
if (num == candidate) {
occurrences++;
}
}
return occurrences > nums.length / 2;
}
}def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count = 1
elif candidate == num:
count += 1
else:
count -= 1
return sum(1 for x in nums if x == candidate) > len(nums) / 2function majorityElement(nums) {
let count = 0;
let candidate = null;
for (let num of nums) {
if (count === 0) {
candidate = num;
count = 1;
} else if (candidate === num) {
count++;
} else {
count--;
}
}
return nums.filter(x => x === candidate).length > nums.length / 2;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.