Majority Element Identifier — Problem Statement & Solution Guide
Problem Description
Given an array of integers, find and return the integer that appears more than half of the time. If no such integer exists, return -1. The input array will have at least one element and at most 10^5 elements.
Examples
Input
[3, 2, 3]
Output
3
Explanation: Step-by-step: with input [3, 2, 3], we first count the occurrences of each number. 3 occurs twice, which is more than half of the total count (3). So, the output is 3.
Input
[2, 2, 1, 1, 1, 2, 2]
Output
2
Explanation: Step-by-step: with input [2, 2, 1, 1, 1, 2, 2], we first count the occurrences of each number. 2 occurs 4 times, which is more than half of the total count (7). So, the output is 2.
Constraints
- 1 <= n <= 5 * 10^4
Optimal Approach & Strategy
Use Boyer-Moore Voting Algorithm. Maintain a candidate and a count. If count is 0, pick current element as candidate. If same, increment count, else decrement. Time O(N), Space O(1).
Brute Force Approach
Count occurrences of each element. Time O(N^2).
Verified Code Solutions
function solution(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--;
}
}
let occurrences = 0;
for (let num of nums) {
if (num === candidate) {
occurrences++;
}
}
return occurrences > nums.length / 2 ? candidate : -1;
}class Solution {
public:
int solution(vector<int>& nums) {
int count = 0;
int candidate = -1;
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 ? candidate : -1;
}
};class Solution {
public int solution(int[] nums) {
int count = 0;
Integer candidate = null;
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 ? candidate : -1;
}
}def solution(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count = 1
elif candidate == num:
count += 1
else:
count -= 1
occurrences = sum(1 for num in nums if num == candidate)
return candidate if occurrences > len(nums) / 2 else -1function solution(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--;
}
}
let occurrences = 0;
for (let num of nums) {
if (num === candidate) {
occurrences++;
}
}
return occurrences > nums.length / 2 ? candidate : -1;
}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.