You are given a sorted array of integers, nums, and an integer target. The task is to determine whether target is a majority element in the array. A majority element is defined as an element that appears more than n / 2 times in the array, where n is the length of nums.
nums is sorted in non-decreasing order.true if target is a majority element, otherwise return false.
The first idea that comes to mind is to count how many times target appears in nums. If this count is greater than n / 2, then target is a majority element.
Since the array is sorted, all occurrences of target will be grouped together. This suggests that we can do better than a simple linear scan, which would take O(n) time.
Instead of checking every element, we can use binary search to efficiently find the first and last positions of target in the array. This allows us to count the number of occurrences in O(log n) time.
In summary, the shift is from a brute-force O(n) approach to an optimized O(log n) approach by leveraging the sorted property of the array.
target in nums.
target in nums.
target appears is last - first + 1. If this count is greater than n / 2, return true; else, return false.
target in O(log n) time, instead of scanning every element.
target is not present, both searches will return -1 or invalid indices, so the count will be zero.
This method is efficient and takes full advantage of the sorted property of the input array.
Example:
nums = [1,2,3,3,3,3,10], target = 3
n / 2 = 3.5.target is a majority element. Return true.
Another Example:
nums = [1,1,2,2,2], target = 1
n / 2 = 2.5false.target. This takes O(n) time and O(1) space.
By leveraging the sorted property of the input array, we can efficiently determine if a target is a majority element using binary search to find its first and last positions. This reduces the time complexity from O(n) to O(log n), making the solution both elegant and efficient. The key insight is to count occurrences using index boundaries rather than scanning the entire array.
class Solution:
def isMajorityElement(self, nums, target):
def find_first(nums, target):
left, right = 0, len(nums) - 1
first = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
first = mid
right = mid - 1
return first
def find_last(nums, target):
left, right = 0, len(nums) - 1
last = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
last = mid
left = mid + 1
return last
first = find_first(nums, target)
if first == -1:
return False
last = find_last(nums, target)
count = last - first + 1
return count > len(nums) // 2
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
int n = nums.size();
int first = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (first == n || nums[first] != target) return false;
int last = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
int count = last - first + 1;
return count > n / 2;
}
};
class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int first = findFirst(nums, target);
if (first == -1) return false;
int last = findLast(nums, target);
int count = last - first + 1;
return count > nums.length / 2;
}
private int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1, first = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
first = mid;
right = mid - 1;
}
}
return first;
}
private int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1, last = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
last = mid;
left = mid + 1;
}
}
return last;
}
}
var isMajorityElement = function(nums, target) {
function findFirst(nums, target) {
let left = 0, right = nums.length - 1, first = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
first = mid;
right = mid - 1;
}
}
return first;
}
function findLast(nums, target) {
let left = 0, right = nums.length - 1, last = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
last = mid;
left = mid + 1;
}
}
return last;
}
let first = findFirst(nums, target);
if (first === -1) return false;
let last = findLast(nums, target);
let count = last - first + 1;
return count > Math.floor(nums.length / 2);
};