Check If a Number Is Majority Element in a Sorted Array Python/Java solution

Python and Java implementations both rely on binary search. First locate the leftmost occurrence of the target, then check whether nums[index + n/2] equals the target while staying within bounds. This produces an O(log n) time solution with constant extra space in both languages.

What is the best approach for Check If a Number Is Majority Element in a Sorted Array?

The best approach uses binary search to find the first occurrence of the target and then checks the element at index start + n/2. If that position contains the same value, the target appears more than half the time. This works because the array is sorted, allowing positional verification instead of counting. The overall time complexity is O(log n) with O(1) extra space.

Is Check If a Number Is Majority Element in a Sorted Array asked at Google/Amazon/Meta?

Majority element and binary search pattern problems commonly appear in interviews at companies like Google, Amazon, and Meta. Variations may ask you to count occurrences in a sorted array or detect majority elements under different constraints. The key skill tested is applying binary search to frequency-related problems.

What data structure is used in Check If a Number Is Majority Element in a Sorted Array?

The problem primarily uses an array as the underlying data structure. The algorithm relies on the sorted property of the array and applies binary search to efficiently locate the target and reason about its frequency.

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

The optimal solution runs in O(log n) time using binary search. You locate the first occurrence of the target and perform a constant-time offset check to confirm the majority condition. Space complexity remains O(1) because the algorithm uses only a few variables.

Description Hints 4 Solution Video 11:55

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

Q: Is Check If a Number Is Majority Element in a Sorted Array easy or hard?

The problem is classified as Easy because the key observation is straightforward once you recognize the sorted property. Most of the work involves applying binary search correctly and understanding why checking the n/2 offset confirms a majority element.

Q: How to solve Check If a Number Is Majority Element in a Sorted Array in O(log n)?

Perform a binary search to find the leftmost occurrence of the target in the sorted array. After finding that index, compute start + n/2 and verify that the element at that position is still the target. If it is, the target appears more than n/2 times. The search step takes O(log n) time and the verification step is O(1).

Easy59.9% acceptance1 companyPremium elsewhere, free here

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 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.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i], target <= 10⁹
nums is sorted in non-decreasing order.

Asked at 1 company

Salesforce

Topics

Array Binary Search

Hints open one at a time

Hint 1

How to check if a given number target is a majority element?.

Hint 2

Find the frequency of target and compare it to the length of the array.

Hint 3

You can find the frequency of an element using Binary Search since the array is sorted.

Hint 4

Using Binary Search, find the first and last occurrences of A. Then just calculate the difference between the indexes of these occurrences.

11:55

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution