Check If a Number Is a Majority Element in a Sorted Array
The problem
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.
Input: nums = [1,2,3,3,3,3,3,4,5], target = 3 Output: true Explanation: The value 3 appears 5 times and the length of the array is 9. Thus, 3 is a majority element because 5 > 9/2 is true.
Input: nums = [7,8,8,8,9,9,9,10,11], target = 8 Output: false Explanation: The value 8 appears 3 times and the length of the array is 9. Thus, 8 is not a majority element because 3 > 9/2 is false.
Input: nums = [3,3,3,3,3,5,5,5,5,5], target = 3
- 1 <= nums.length <= 1000
- 1 <= nums[i], target <= 10^9
- nums is sorted in non-decreasing order.
cpp
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
// Your code goes here
}
};java
class Solution {
public boolean isMajorityElement(int[] nums, int target) {
// Your code goes here
}
}python
class Solution:
def isMajorityElement(self, nums, target):
# Your code goes herejavascript
/**
* @param {number[]} nums - Sorted array of numbers
* @param {number} target - Target number to check
* @return {boolean} - Whether target is a majority element
*/
function isMajorityElement(nums, target) {
// Your code goes here
}csharp
public class Solution {
public bool IsMajorityElement(int[] nums, int target) {
// Your code goes here
}
}go
func isMajorityElement(nums []int, target int) bool {
}Stuck? Show a way to structure it+
- 01Find the first target occurrence with lower bound.
- 02Check that target exists.
- 03Compare position first+n/2 against target.
- 04Return whether it remains target.
Reference answer
Then expect these follow-ups
How would you return the exact count?
Tests: upper bound
What changes for a threshold other than half?
Tests: generalization
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question