💬 Discord
Sign In
NeetCode #267LC-1150EasyBinary SearchNC Algo100
← Back to All Problems

#267 · #1150 · Check If a Number Is Majority Element in a Sorted Array(检查一个数是否在数组中占绝大多数)

📌 Problem Statement & Constraints

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is the majority element (appears more than n / 2 times). Constraints: 1 <= nums.length <= 10^4, -10^9 <= nums[i], target <= 10^9.

💡 Core Algorithmic Approaches

  1. Binary search for the lower bound of target (bisect_left) and the upper bound (bisect_right).
  2. The difference is the number of occurrences, which can be compared with n / 2 directly.
  3. This is O(log n) rather than the O(n) linear count.
  4. The standard Boyer-Moore voting algorithm is not applicable here, because we need the count of a specific value.

💻 Benchmark Python3 Implementation

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        from bisect import bisect_left, bisect_right
        lo = bisect_left(nums, target)     # first index with value >= target
        hi = bisect_right(nums, target)    # first index with value > target
        return (hi - lo) * 2 > len(nums)   # strictly more than half

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): two binary searches.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Using >= len(nums) / 2: the majority requires strictly more than half, so * 2 > is the right test.
  • Scanning linearly to count occurrences: O(n), which defeats the point of the sorted input.
  • Using bisect_right for the lower bound: that would skip equal values.
  • Assuming target is present: if it is absent, both bounds are equal and the difference is 0, correctly returning false.