Check If A Number Is Majority Element In A Sorted Array - Leetcode Solution

Problem Statement:

Given an array nums sorted in non-decreasing order, and an integer target, return True if target is a majority element, or False otherwise.

A majority element is an element that appears more than n / 2 times in an array, where n is the length of the array.

Example 1: Input: nums = [2,4,5,5,5,5,5,6,6], target = 5 Output: true

Example 2: Input: nums = [10,100,101,101], target = 101 Output: false

Solution:

Since the array is sorted in non-decreasing order, we can use the binary search technique to find the first and last index of the target element in the array. Once we have these indices, we can calculate the frequency of the target element in the array. If the frequency is greater than n / 2, where n is the length of the array, then the target element is a majority element and we return True. Otherwise, we return False.

Let's write code for this solution:

class Solution: def isMajorityElement(self, nums: List[int], target: int) -> bool: n = len(nums) left = self.first_index(nums, target, 0, n-1) if left == -1: return False right = self.last_index(nums, target, 0, n-1) frequency = right - left + 1 if frequency > n / 2: return True return False

def first_index(self, nums: List[int], target: int, start: int, end: int) -> int:
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            if mid == 0 or nums[mid-1] != target:
                return mid
            else:
                end = mid - 1
        elif nums[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return -1

def last_index(self, nums: List[int], target: int, start: int, end: int) -> int:
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            if mid == len(nums)-1 or nums[mid+1] != target:
                return mid
            else:
                start = mid + 1
        elif nums[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return -1

In the above code, we have used two helper functions first_index and last_index to find the first and last index of the target element in the array, respectively. These helper functions use binary search to find the indices.

Time Complexity: O(log n), where n is the length of the array. Space Complexity: O(1).

Therefore, the given problem can be solved using binary search in O(log n) time complexity.

1