Check If a Number Is Majority Element in a Sorted Array

Check If a Number Is Majority Element in a Sorted Array

What is this problem about?

The "Check If a Number Is Majority Element in a Sorted Array interview question" asks you to verify if a target number target appears more than $n/2$ times in a given array. The array is guaranteed to be sorted in non-decreasing order. This "Majority Element coding problem" is a variation of the standard majority element task, but the "sorted" property allows for a much faster solution than a simple count.

Why is this asked in interviews?

Salesforce and other companies use this problem to see if a candidate can optimize a search. While a linear scan is $O(N)$, the sorted property should immediately trigger thoughts of Binary Search, which is $O(\log N)$. It evaluates your ability to find boundaries in an array and use them to calculate frequency.

Algorithmic pattern used

This problem uses the Binary Search (Find First/Last Occurrence) pattern.

1. Find First: Use binary search to find the first index where target appears.
2. Index Math: If the target is the majority element, it must appear at index first_index + n/2.
3. Validation: Check if arr[first_index + n/2] is equal to target. Because the array is sorted, if the element at the "halfway jump" from the start is the same, then every element in between must also be the target.

Example explanation

Array: [2, 4, 5, 5, 5, 5, 5, 6, 6], Target: 5, $n=9$.

1. Threshold: $n/2 = 4.5$. We need at least 5 occurrences.
2. Binary Search: First index of 5 is 2.
3. Check index: first_index + n/2 = 2 + 4 = 6.
4. arr[6] is 5. Result: True. (If it were not the majority element, the element at index 6 would have been greater than 5).

Common mistakes candidates make

• Linear Scan: Using a simple loop to count occurrences. While correct, it misses the $O(\log N)$ optimization opportunity that interviewers look for.
• Index Out of Bounds: Not checking if first_index + n/2 exceeds the array length before accessing it.
• Forgetting the Sorted Property: Not using the "jump" trick and instead finding both the first and last indices, which is still $O(\log N)$ but slightly less efficient than the single-search check.

Interview preparation tip

Whenever you see "Sorted Array" and "Count" or "Search," think Binary Search. Master the ability to find the leftmost and rightmost occurrences of a value, as this is a fundamental "Array interview pattern" skill.