What is the time complexity of LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array?

The Python solution on this page runs in O(\log n).

What is the space complexity of LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array?

The Python solution on this page uses O(1) auxiliary space.

Check If a Number Is Majority Element in a Sorted Array — LeetCode 1150 Python Solution

EasyLeetCode PremiumArrayBinary Search

Problem: #1150
Pattern: Monotonic Stack
Reading time: 2 min
Source: leetcode.com

The problem

Given an integer 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 in an array nums is an element that appears more than nums.length / 2 times in the array.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(\log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array?: LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array is rated Easy on LeetCode.
What is the time complexity of LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array?: The Python solution on this page runs in O(\log n).
What is the space complexity of LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array cover?: LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array is tagged Array and Binary Search on LeetCode.
Is LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array a premium problem?: Yes. LeetCode 1150. Check If a Number Is Majority Element in a Sorted Array is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.