Majority Element Identifier — Problem Statement & Solution Guide
Problem Description
You are given an integer array arr containing N numbers. Your task is to identify whether there exists a majority element within the sequence. An element is considered a majority element if its frequency of occurrence is strictly greater than N / 2 (where N is the total number of elements in the array).
If such an element exists, return its value. Otherwise, return -1 to indicate that no element meets the required frequency threshold. The array may contain positive integers, negative integers, and zeros.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Majority Element Identifier"
WHY DOES IT MATTER?
Mastering element cancellation techniques transitions developers from relying on memory-intensive hash tables to designing ultra-efficient O(1) auxiliary space algorithms.
OPTIMIZATION CHALLENGE
The key insight is realizing that tracking an absolute frequency map is unnecessary; we only need to maintain a single relative balance state between the lead candidate and non-candidate elements.
REAL-WORLD CONNECTION
In fault-tolerant distributed consensus systems (like Raft or Paxos) and stream telemetry, identifying majority votes or dominant error codes under tight memory limits relies on majority voting dynamics.
Always clarify with the interviewer whether a majority element is guaranteed to exist. If it is guaranteed, one pass suffices; if not guaranteed, explicitly code the second verification pass.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The Majority Element problem asks us to find an element that appears more than half the time (frequency > N / 2) in an array of size N. A naive solution uses two nested loops to count the occurrence of every element, leading to an O(N^2) time complexity. For large inputs (e.g., N = 10^5), this brute-force method requires billions of operations, causing a Time Limit Exceeded (TLE) error. Using a Hash Map reduces the time complexity to O(N) by storing element frequencies in a single pass, but requires O(N) auxiliary space.
To achieve both optimal O(N) time and O(1) space, we leverage the Boyer-Moore Voting Algorithm. The core theory behind Boyer-Moore rests on the principle of cancellation: if we pair distinct elements and remove them from consideration, a majority element (appearing strictly more than N / 2 times) will always remain in the pool. By maintaining a running candidate and a counter, distinct elements effectively cancel each other out, leaving the majority element as the final candidate.
Since the problem statement indicates that a majority element might not exist, the algorithm requires two phases: Candidate Selection using Boyer-Moore, followed by Candidate Verification. The verification step requires a second simple linear scan to count the exact occurrences of the candidate and verify that frequency strictly exceeds N / 2. If it does not, we return -1.
Interview Questions on This Problem
Q1How would you modify the Boyer-Moore Voting Algorithm if the problem required finding elements that appear more than N / 3 times?
To find elements appearing more than N / 3 times, there can be at most two such majority elements. We extend Boyer-Moore by keeping track of two candidate variables and two corresponding count variables. In a single pass, if an element matches either candidate, we increment its count; if a count is zero, we assign the new element as that candidate; otherwise, if the current element differs from both, we decrement both counts. Finally, a second verification pass counts exact occurrences for both candidates to confirm if their frequencies strictly exceed N / 3.
Q2Can the Boyer-Moore Voting Algorithm be applied to distributed data streams stored across multiple server nodes?
Yes. Using a MapReduce or stream-processing architecture, each worker node can run the Boyer-Moore algorithm on its local partition to output a local candidate along with its remaining candidate count. These local summaries can then be reduced and merged centrally. However, because local candidates might differ, a secondary consensus pass (or global frequency count pass across nodes) is required to accurately compute the global majority element.
Q3Why is the second verification pass mandatory when a majority element is not guaranteed to exist in the array?
Boyer-Moore always outputs a final candidate value at the end of the array traversal, even if no element actually appears strictly more than N / 2 times. For instance, in the array [1, 2, 3], the algorithm might terminate with 3 as the candidate, even though its frequency is only 1 (which is <= 3 / 2). Without a second pass to explicitly count frequency and check the > N / 2 condition, the algorithm would incorrectly return 3 instead of -1.
Examples
Input
arr = [4, -2, 4, 4, 1, 4, 4]
Output
4
Explanation: The array contains N = 7 elements. The threshold for a majority element is strictly greater than 7 / 2 = 3.5 (i.e., at least 4 occurrences). The number 4 appears 5 times, which exceeds 3.5. Therefore, the output is 4.
Input
arr = [10, 20, 10, 30, 20, 30]
Output
-1
Explanation: The array length N = 6. To be a majority element, an integer must appear strictly more than 6 / 2 = 3 times (at least 4 times). The numbers 10, 20, and 30 each appear only 2 times. Since no number appears more than 3 times, the output is -1.
Input
arr = [-5, -5, 0, -5]
Output
-5
Explanation: The array length N = 4. The required frequency must be strictly greater than 4 / 2 = 2. The integer -5 occurs 3 times, satisfying the majority condition. Thus, the output is -5.
Input
arr = [7, 7, 7, 8, 8, 8]
Output
-1
Explanation: The array length N = 6. A majority element must appear strictly more than 3 times. Both 7 and 8 appear exactly 3 times, which does not strictly exceed 3. Hence, the output is -1.
Constraints
- 1 <= arr.length <= 10^5
- -10^9 <= arr[i] <= 10^9
Optimal Approach & Strategy
Apply Boyer-Moore's Voting Algorithm in a single pass to identify a candidate element by maintaining a running vote counter. Run a second linear verification pass to validate if the candidate's actual frequency strictly exceeds N / 2, returning -1 if it does not.
Brute Force Approach
Iterate through each element of the array and count its total frequency by scanning the rest of the array using a nested loop. Return the element if its count strictly exceeds N / 2, resulting in an O(N^2) time complexity.
Verified Code Solutions
const fs = require('fs');
function majorityElement(arr) {
const n = arr.length;
if (n === 0) return -1;
const counts = new Map();
for (const num of arr) {
const count = (counts.get(num) || 0) + 1;
if (count > Math.floor(n / 2)) {
return num;
}
counts.set(num, count);
}
return -1;
}
function main() {
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();
if (!input) {
console.log(-1);
return;
}
const arr = input.split(/\s+/).map(Number);
console.log(majorityElement(arr));
}
main();#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <string>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& arr) {
int n = arr.size();
if (n == 0) return -1;
unordered_map<int, int> counts;
for (int num : arr) {
counts[num]++;
if (counts[num] > n / 2) {
return num;
}
}
return -1;
}
};
int main() {
string line;
if (getline(cin, line)) {
if (line.empty()) {
cout << -1 << endl;
return 0;
}
stringstream ss(line);
vector<int> arr;
int num;
while (ss >> num) {
arr.push_back(num);
}
Solution sol;
cout << sol.majorityElement(arr) << endl;
}
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static int majorityElement(int[] arr) {
int n = arr.length;
if (n == 0) return -1;
Map<Integer, Integer> counts = new HashMap<>();
for (int num : arr) {
int count = counts.getOrDefault(num, 0) + 1;
if (count > n / 2) {
return num;
}
counts.put(num, count);
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.trim().isEmpty()) {
System.out.println(-1);
return;
}
String[] parts = line.trim().split("\\s+");
int[] arr = new int[parts.length];
for (int i = 0; i < parts.length; i++) {
arr[i] = Integer.parseInt(parts[i]);
}
System.out.println(majorityElement(arr));
}
}import sys
def majority_element(arr):
n = len(arr)
if n == 0:
return -1
counts = {}
for num in arr:
counts[num] = counts.get(num, 0) + 1
if counts[num] > n // 2:
return num
return -1
def main():
input_data = sys.stdin.read().strip()
if not input_data:
print(-1)
return
arr = list(map(int, input_data.split()))
print(majority_element(arr))
if __name__ == '__main__':
main()const fs = require('fs');
function majorityElement(arr) {
const n = arr.length;
if (n === 0) return -1;
const counts = new Map();
for (const num of arr) {
const count = (counts.get(num) || 0) + 1;
if (count > Math.floor(n / 2)) {
return num;
}
counts.set(num, count);
}
return -1;
}
function main() {
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();
if (!input) {
console.log(-1);
return;
}
const arr = input.split(/\s+/).map(Number);
console.log(majorityElement(arr));
}
main();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.