Solutions

1. Frequency Count

Intuition

A majority element appears more than half the time. The simplest approach is to count how many times the target appears in the array by scanning through all elements. If the count exceeds n/2, the target is a majority element.

Algorithm

Initialize a counter to 0.
Iterate through the array:
- Increment the counter each time we encounter the target.
Return true if the count is greater than half the array length, false otherwise.

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        count = 0
        for num in nums:
            count = count + 1 if num == target else count
        
        return count > len(nums) // 2

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$ constant space

Where $N$ is the size of nums.

2. Binary Search (Two Pass)

Intuition

Since the array is sorted, all occurrences of the target are contiguous. We can use binary search to find the first and last occurrence of the target. The count is simply (lastIndex - firstIndex + 1), which we compare against n/2.

Algorithm

Use lower_bound to find the index of the first element >= target.
Use upper_bound to find the index of the first element > target.
The count of target is (upper_bound - lower_bound).
Return true if this count is greater than n/2.

class Solution:
    def lower_bound(self, nums: List[int], target: int) -> int:
        """
        Returns the index of the first element equal to or greater than the target.
        If there is no instance of the target in the list, it returns the length of the list.
        """
        start = 0
        end = len(nums) - 1
        index = len(nums)
        
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] >= target:
                end = mid - 1
                index = mid
            else:
                start = mid + 1
        
        return index
    
    def upper_bound(self, nums: List[int], target: int) -> int:
        """
        Returns the index of the first element greater than the target.
        If there is no instance of the target in the list, it returns the length of the list.
        """
        start = 0
        end = len(nums) - 1
        index = len(nums)
        
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] > target:
                end = mid - 1
                index = mid
            else:
                start = mid + 1
        
        return index
    
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        first_index = self.lower_bound(nums, target)
        next_to_last_index = self.upper_bound(nums, target)
        return next_to_last_index - first_index > len(nums) // 2

Time & Space Complexity

Time complexity: $O(\log N)$
Space complexity: $O(1)$ constant space

Where $N$ is the size of nums.

3. Binary Search (One Pass)

Intuition

If the target is a majority element, it must occupy more than half the array positions. This means if we find the first occurrence at index i, the element at index i + n/2 must also be the target. We only need one binary search to find the first occurrence, then check this specific position.

Algorithm

Use lower_bound to find the first occurrence of the target at index i.
Calculate the position i + n/2 (where n is the array length).
If this position is within bounds and the element at that position equals the target, return true.
Otherwise, return false.

class Solution:
    def lower_bound(self, nums: List[int], target: int) -> int:
        """
        Returns the index of the first element that is equal to or greater than the target.
        If there is no instance of the target in the list, it returns the length of the list.
        """
        start = 0
        end = len(nums) - 1
        index = len(nums)
        
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] >= target:
                end = mid - 1
                index = mid
            else:
                start = mid + 1
        
        return index
    
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        first_index = self.lower_bound(nums, target)
        return first_index + len(nums) // 2 < len(nums) and nums[first_index + len(nums) // 2] == target

Time & Space Complexity

Time complexity: $O(\log N)$
Space complexity: $O(1)$ constant space

Where $N$ is the size of nums.