Check If a Number Is Majority Element in a Sorted Array
Easy · Binary Search · Explanation and code example
Binary Search (One Pass)
How it works
If the target is a majority element, it must occupy more than half the array positions. This means if we find the first occurrence at index i, the element at index i + n/2 must also be the target. We only need one binary search to find the first occurrence, then check this specific position.
Steps
- Use
lower_boundto find the first occurrence of the target at indexi. - Calculate the position
i+n/2 (wherenis the array length). - If this position is within bounds and the element at that position equals the target, return
true. - Otherwise, return
false.
Complexity
- Time complexity:
O(log N) - Space complexity:
O(1)constant space
Where
Nis the size ofnums.
Things to watch for
Using >= Instead of > for Majority Check
The majority element must appear more than n/2 times, not greater than or equal to. Using count >= n/2 will incorrectly return true for elements that appear exactly half the time.
Not Leveraging the Sorted Property
Since the array is sorted, all occurrences of the target are contiguous. A common mistake is to use a linear scan when binary search can find the first and last occurrence in O(log N) time. Additionally, forgetting that you only need to check if nums[first_index + n//2] == target after finding the first occurrence wastes an extra binary search.
Python code example
from typing import List
class Solution:
def lower_bound(self, nums: List[int], target: int) -> int:
"""
Returns the index of the first element that is equal to or greater than the target.
If there is no instance of the target in the list, it returns the length of the list.
"""
start = 0
end = len(nums) - 1
index = len(nums)
while start <= end:
mid = (start + end) // 2
if nums[mid] >= target:
end = mid - 1
index = mid
else:
start = mid + 1
return index
def isMajorityElement(self, nums: List[int], target: int) -> bool:
first_index = self.lower_bound(nums, target)
return first_index + len(nums) // 2 < len(nums) and nums[first_index + len(nums) // 2] == target
C++ code example
class Solution {
public:
// Returns the index of the first element equal to or greater than the target.
// If there is no instance of the target in the list, it returns the length of the list.
int lower_bound(vector<int>& nums, int target) {
int start = 0;
int end = nums.size() - 1;
int index = nums.size();
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] >= target) {
end = mid - 1;
index = mid;
} else {
start = mid + 1;
}
}
return index;
}
bool isMajorityElement(vector<int>& nums, int target) {
int firstIndex = lower_bound(nums, target);
return firstIndex + nums.size() / 2 < nums.size() && nums[firstIndex + nums.size() / 2] == target;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.