Check If a Number Is Majority Element in a Sorted Array - Solution & Explanation
Problem Statement
Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.
A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.
Example 1:
Input: nums = [2,4,5,5,5,5,5,6,6], target = 5 Output: true Explanation: The value 5 appears 5 times and the length of the array is 9. Thus, 5 is a majority element because 5 > 9/2 is true.
Example 2:
Input: nums = [10,100,101,101], target = 101 Output: false Explanation: The value 101 appears 2 times and the length of the array is 4. Thus, 101 is not a majority element because 2 > 4/2 is false.
Constraints:
1 <= nums.length <= 10001 <= nums[i], target <= 109numsis sorted in non-decreasing order.
Approach Overview
Problem Overview: You are given a sorted integer array and a target value. The task is to determine whether the target appears more than n / 2 times. Because the array is already sorted, the occurrences of any value are grouped together, which allows efficient searching using binary search instead of scanning the entire array.
Approach 1: Binary Search (O(log n) time, O(1) space)
Use binary search to locate the first occurrence of the target. Once you know where the target begins, compute the index start + n/2. If that index is within bounds and the value at that position is still the target, the element appears more than half the time. The insight comes from the sorted property: if a number is a majority element, the element exactly n/2 positions ahead of its first occurrence must also be the same value. This avoids counting occurrences and leverages the structure of the array.
Approach 2: Binary Search (Optimized) (O(log n) time, O(1) space)
Another approach performs two binary searches to find the leftmost and rightmost occurrences of the target. The difference between these indices gives the total frequency of the element. If right - left + 1 > n/2, the target is the majority element. This technique is a classic pattern for counting duplicates in a sorted array using binary search. While it performs two searches instead of one, the complexity remains logarithmic and the implementation is straightforward to reason about.
Recommended for interviews: The single-search majority check (finding the first occurrence and verifying the n/2 offset) is the most elegant solution. It demonstrates that you understand how sorted order enables positional reasoning instead of brute-force counting. Showing the two-boundary binary search method is also acceptable, but the optimized offset trick usually stands out as the cleanest solution.
Approach 1: Binary Search
We notice that the elements in the array nums are non-decreasing, that is, the elements in the array nums are monotonically increasing. Therefore, we can use the method of binary search to find the index left of the first element in the array nums that is greater than or equal to target, and the index right of the first element in the array nums that is greater than target. If right - left > \frac{n}{2}, it means that the number of occurrences of the element target in the array nums exceeds half of the length of the array, so return true, otherwise return false.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Binary Search (Optimized)
In Solution 1, we used binary search twice to find the index left of the first element in the array nums that is greater than or equal to target, and the index right of the first element in the array nums that is greater than target. However, we can use binary search once to find the index left of the first element in the array nums that is greater than or equal to target, and then judge whether nums[left + \frac{n}{2}] is equal to target. If they are equal, it means that the number of occurrences of the element target in the array nums exceeds half of the length of the array, so return true, otherwise return false.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search | — |
| Binary Search (Optimized) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search (first occurrence + offset check) | O(log n) | O(1) | Best choice when the array is sorted and you want the fastest majority check |
| Binary Search (leftmost and rightmost bounds) | O(log n) | O(1) | Useful when you need the exact frequency of the target in a sorted array |
Video Solution
LeetCode 1150: Check If a Number Is Majority Element in a Sorted Array - Interview Prep Ep 48 • Fisher Coder • 1,686 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Check If a Number Is Majority Element in a Sorted Array easy or hard?
Check If a Number Is Majority Element in a Sorted Array Python/Java solution
How to solve Check If a Number Is Majority Element in a Sorted Array in O(log n)?
What is the best approach for Check If a Number Is Majority Element in a Sorted Array?
Is Check If a Number Is Majority Element in a Sorted Array asked at Google/Amazon/Meta?
What data structure is used in Check If a Number Is Majority Element in a Sorted Array?
What is the time complexity of Check If a Number Is Majority Element in a Sorted Array?
Ready to solve this problem?
Practice Check If a Number Is Majority Element in a Sorted Array with our built-in code editor and test cases.
Practice on FleetCode