Majority Element Threshold — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, identify the element that occurs strictly more than half of the array length. If such an element exists, return its value; otherwise return the string "No dominant candidate". The solution must run in linear time and use O(1) extra space, which can be achieved with the Boyer‑Moore voting technique.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Majority Element Threshold"
WHY DOES IT MATTER?
The pattern exemplifies constant‑space streaming algorithms, a cornerstone for processing massive logs, sensor data, or real‑time analytics where storing the entire dataset is infeasible.
OPTIMIZATION CHALLENGE
Recognizing that pairs of different elements cancel each other eliminates the need for full frequency tables, collapsing the problem to a simple counter update—a classic reduction from O(n) space to O(1).
REAL-WORLD CONNECTION
Think of a vote tally in a large election where you only keep track of the current front‑runner and the margin; every time a different candidate appears, the margin shrinks, mirroring how distributed consensus protocols prune conflicting proposals.
During an interview, run the algorithm mentally on a short example first; it demonstrates your grasp of the cancellation intuition and helps you catch off‑by‑one errors in the verification step.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Boyer‑Moore majority vote algorithm leverages a cancellation principle: if we pair each occurrence of a non‑candidate element with an occurrence of the current candidate, they neutralize each other. After a full linear scan, any element that appears more than ⌊n/2⌋ times will survive as the sole candidate because it cannot be completely cancelled out. Naïve counting using a hash map or sorting requires O(n) extra space or O(n log n) time, which becomes prohibitive for massive streams or memory‑constrained environments. The optimal paradigm treats the problem as a streaming majority detection, maintaining only a single counter and a potential candidate, thus achieving O(1) auxiliary space while still guaranteeing linear time.
The algorithm proceeds in two passes: the first identifies a candidate by incrementing the counter when the current element matches the candidate and decrementing otherwise; when the counter hits zero, we adopt the next element as the new candidate. The second pass verifies that the candidate truly exceeds the half‑length threshold, protecting against cases where no majority exists. This two‑phase verification is essential because the cancellation process alone only guarantees a potential majority, not its existence.
Interview Questions on This Problem
Q1How does the Boyer‑Moore voting algorithm guarantee O(1) space while still correctly identifying a majority element?
It maintains only two variables—a candidate and a count—so memory usage does not grow with input size. The cancellation logic ensures that any element occurring more than n/2 times cannot be fully cancelled, leaving it as the final candidate, which is then verified in a second pass.
Q2If the array length is even and no element appears more than n/2 times, what does the algorithm return and why?
After the first pass you obtain a candidate, but the second verification pass will count its occurrences and discover it does not exceed n/2, so you return the sentinel string "No dominant candidate".
Q3Can the Boyer‑Moore technique be adapted to find elements occurring more than ⌊n/3⌋ times? Briefly outline the modification.
Yes; you keep up to two candidates and two counters because at most two distinct elements can exceed n/3. The update rules are similar: increment matching counters, decrement both when the current element matches neither and both counters are non‑zero, otherwise replace a zero‑counter candidate. A final verification pass confirms any true n/3 majorities.
Examples
Input
[3,3,4,2,3,3,3]
Output
3
Explanation: First pass selects a candidate by pairing different values; after processing all elements the candidate is 3. A second pass counts its occurrences (5) which exceeds 7/2=3.5, so 3 is returned.
Input
[1,2,3,4]
Output
No dominant candidate
Explanation: The voting phase ends with candidate 4, but its count in the verification pass is 1, which is not greater than 4/2=2. Hence no element satisfies the majority condition.
Input
[5,5,5,5]
Output
5
Explanation: All elements are identical; the candidate after the first pass is 5 and its count (4) exceeds 4/2=2, so 5 is returned.
Constraints
- 1 <= nums.length <= 200000
- -10^9 <= nums[i] <= 10^9
- Time complexity O(n)
- Auxiliary space O(1)
Optimal Approach & Strategy
Use Boyer‑Moore voting to find a candidate in one pass and verify it in a second pass, achieving O(n) time and O(1) extra space.
Brute Force Approach
Count frequencies of all numbers using a hash map or sort the array and scan for a run longer than n/2.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function majorityElement(arr){
let count=0, candidate=null;
for(const num of arr){
if(count===0){candidate=num; count=1;}
else if(num===candidate) ++count;
else --count;
}
let freq=0;
for(const num of arr) if(num===candidate) ++freq;
return freq>Math.floor(arr.length/2)? String(candidate):'No dominant candidate';
}
if(n>0) console.log(majorityElement(nums));
else console.log('No dominant candidate');#include <bits/stdc++.h>
using namespace std;
string majorityElement(const vector<int>& nums){
int count=0, candidate=0;
for(int num: nums){
if(count==0){candidate=num; count=1;}
else if(num==candidate) ++count;
else --count;
}
int freq=0;
for(int num: nums) if(num==candidate) ++freq;
if(freq> (int)nums.size()/2) return to_string(candidate);
return "No dominant candidate";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i)cin>>nums[i];
cout<<majorityElement(nums);
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static String majorityElement(int[] nums){
int count=0, candidate=0;
for(int num: nums){
if(count==0){candidate=num; count=1;}
else if(num==candidate) ++count;
else --count;
}
int freq=0;
for(int num: nums) if(num==candidate) ++freq;
return freq>nums.length/2? String.valueOf(candidate):"No dominant candidate";
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()){
System.out.print("No dominant candidate");
return;
}
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
int idx=0;
while(st.hasMoreTokens() && idx<n){
nums[idx++] = Integer.parseInt(st.nextToken());
}
while(idx<n){
st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens() && idx<n){
nums[idx++] = Integer.parseInt(st.nextToken());
}
}
System.out.print(majorityElement(nums));
}
}
import sys
def majority_element(nums):
count=0
candidate=None
for num in nums:
if count==0:
candidate=num
count=1
elif num==candidate:
count+=1
else:
count-=1
freq=sum(1 for x in nums if x==candidate)
return str(candidate) if freq>len(nums)//2 else 'No dominant candidate'
def main():
data=sys.stdin.read().strip().split()
if not data:
print('No dominant candidate')
return
n=int(data[0])
nums=list(map(int,data[1:1+n]))
print(majority_element(nums))
if __name__=='__main__':
main()
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function majorityElement(arr){
let count=0, candidate=null;
for(const num of arr){
if(count===0){candidate=num; count=1;}
else if(num===candidate) ++count;
else --count;
}
let freq=0;
for(const num of arr) if(num===candidate) ++freq;
return freq>Math.floor(arr.length/2)? String(candidate):'No dominant candidate';
}
if(n>0) console.log(majorityElement(nums));
else console.log('No dominant candidate');
Asked in Top Tech Interviews
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.