Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Search - Finding elements or boundaries in sorted arrays in O(log N) time
- Lower/Upper Bound - Using binary search variants to find first and last occurrences of a target
- Sorted Array Properties - Leveraging the fact that duplicate elements are contiguous in sorted arrays
1. Frequency Count
Intuition
A majority element appears more than half the time. The simplest approach is to count how many times the target appears in the array by scanning through all elements. If the count exceeds n/2, the target is a majority element.
Algorithm
- Initialize a counter to 0.
- Iterate through the array:
- Increment the counter each time we encounter the target.
- Return
trueif the count is greater than half the array length,falseotherwise.
Time & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the size of
nums.
2. Binary Search (Two Pass)
Intuition
Since the array is sorted, all occurrences of the target are contiguous. We can use binary search to find the first and last occurrence of the target. The count is simply (lastIndex - firstIndex + 1), which we compare against n/2.
Algorithm
- Use
lower_boundto find the index of the first element >= target. - Use
upper_boundto find the index of the first element > target. - The count of target is (
upper_bound-lower_bound). - Return
trueif this count is greater thann/2.
class Solution:
def lower_bound(self, nums: List[int], target: int) -> int:
"""
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.
"""
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 upper_bound(self, nums: List[int], target: int) -> int:
"""
Returns the index of the first element 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)
next_to_last_index = self.upper_bound(nums, target)
return next_to_last_index - first_index > len(nums) // 2Time & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the size of
nums.
3. Binary Search (One Pass)
Intuition
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.
Algorithm
- 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.
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] == targetTime & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the size of
nums.
Common Pitfalls
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.
# Wrong: count >= len(nums) // 2
# Correct:
return count > len(nums) // 2Not 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.