Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1150.html

1150. Check If a Number Is Majority Element in a Sorted Array

Level

Easy

Description

Given an array nums sorted in non-decreasing order, and a number target, return True if and only if target is a majority element.

A majority element is an element that appears more than N/2 times in an array of length N.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5

Output: true

Explanation:

The value 5 appears 5 times and the length of the array is 9.

Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

Input: nums = [10,100,101,101], target = 101

Output: false

Explanation:

The value 101 appears 2 times and the length of the array is 4.

Thus, 101 is not a majority element because 2 > 4/2 is false.

Note:

  1. 1 <= nums.length <= 1000
  2. 1 <= nums[i] <= 10^9
  3. 1 <= target <= 10^9

Solution

Use binary search to find the leftmost index and the rightmost index of target, and calculate how many times target appears. If target appears more than half of the array’s length, then return true. Otherwise, return false.

  • class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int length = nums.length;
        int leftIndex = findLeft(nums, target);
        int rightIndex = findRight(nums, target);
        if (leftIndex < 0 && rightIndex < 0)
            return false;
        else {
            int majorityCount = rightIndex - leftIndex + 1;
            return majorityCount > length / 2;
        }
    }

    public int findLeft(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                if (mid - 1 >= low && nums[mid - 1] == target)
                    high = mid - 1;
                else
                    return mid;
            } else if (num < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -low - 1;
    }

    public int findRight(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                if (mid + 1 <= high && nums[mid + 1] == target)
                    low = mid + 1;
                else
                    return mid;
            } else if (num < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -low - 1;
    }
}

  • // OJ: https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    bool isMajorityElement(vector<int>& A, int target) {
        return upper_bound(begin(A), end(A), target) - lower_bound(begin(A), end(A), target) > A.size() / 2;
    }
};

  • class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left = bisect_left(nums, target)
        right = bisect_right(nums, target)
        return right - left > len(nums) // 2



  • func isMajorityElement(nums []int, target int) bool {
	n := len(nums)
	left := sort.Search(n, func(i int) bool { return nums[i] >= target })
	right := sort.Search(n, func(i int) bool { return nums[i] > target })
	return right-left > n/2
}

  • function isMajorityElement(nums: number[], target: number): boolean {
    const search = (x: number) => {
        let left = 0;
        let right = nums.length;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    const left = search(target);
    const right = search(target + 1);
    return right - left > nums.length >> 1;
}

All Problems

All Solutions