We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check If a Number Is Majority Element in a Sorted Array

Number: 1102

Difficulty: Easy

Paid? Yes

Companies: Salesforce

Problem Description

Given a sorted integer array and a target value, determine if the target is a majority element in the array. A majority element is an element that appears more than ⌊n/2⌋ times in the array, where n is the length of the array.

Key Insights

  • The array is sorted, which allows efficient location of the target using binary search.
  • Instead of counting all occurrences, we can find the leftmost index of the target and check the element at index (leftIndex + n/2).
  • If the target is truly a majority element, the element at that calculated index will also be the target.

Space and Time Complexity

Time Complexity: O(log n), due to using binary search.
Space Complexity: O(1), as only a constant amount of extra space is used.

Solution

We first perform a binary search to locate the leftmost occurrence of the target in the sorted array. Once the leftmost index is found, we compute the index at leftIndex + n/2. If this index is within bounds and its element is equal to the target, then target appears more than n/2 times in the array, qualifying it as a majority element. This method leverages the sorted property to avoid a full count, resulting in an efficient solution.

Code Solutions

# Function to determine if target is a majority element
def isMajorityElement(nums, target):
    # Perform binary search to find the leftmost occurrence of target
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # left is now the smallest index such that nums[left] >= target
    if left < len(nums) and nums[left] == target:
        majorityIndex = left + len(nums) // 2
        # Check if the element at the computed index is target
        if majorityIndex < len(nums) and nums[majorityIndex] == target:
            return True
    return False

# Example usage
print(isMajorityElement([2,4,5,5,5,5,5,6,6], 5))   # Output: True
print(isMajorityElement([10,100,101,101], 101))     # Output: False
← Back to All Questions