Check If a Number Is Majority Element in a Sorted Array

We can solve this problem by following these steps:

  1. Calculate the Majority Threshold: Determine the number of times the target element must appear to be a majority. This will be more than half the length of the array.

  2. Count the Occurrences of the Target: Since the array is sorted, we can quickly count how many times the target appears in the array.

  3. Compare the Count with the Threshold: Compare the count of occurrences with the threshold to determine if the target is a majority element.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        # Calculate the majority threshold
        majority_threshold = len(nums) // 2

        # Initialize the counter for the target
        count = 0

        # Iterate through the array
        for num in nums:
            # If the number matches the target, increment the count
            if num == target:
                count += 1
                # If count exceeds the majority threshold, return True
                if count > majority_threshold:
                    return True
            # If we have crossed the target value, no need to check further
            elif num > target:
                break

        # If count does not exceed the majority threshold, return False
        return False

Explanation:

  • The loop iterates through the array until it either finds enough occurrences of the target to determine it’s a majority or until it encounters a number greater than the target.
  • The majority_threshold is set as half the length of the array, and the target must appear more times than this threshold to be considered a majority.
  • If the loop completes without finding enough occurrences of the target, the function returns False.

The time complexity of this approach is O(n), where n is the length of the array. Since the array is sorted, we can optimize this further by using binary search, but the given code is simple and understandable for beginners.