Watch 10 video solutions for Element Appearing More Than 25% In Sorted Array, a easy level problem involving Array. This walkthrough by codestorywithMIK has 3,119 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6
Example 2:
Input: arr = [1,1] Output: 1
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 105Problem Overview: Given a sorted integer array, exactly one element appears more than 25% of the time. Your job is to return that element. The sorted order is the key constraint: equal values appear in contiguous blocks, which makes counting and boundary checks efficient.
Approach 1: Linear Scan Approach (O(n) time, O(1) space)
The simplest solution scans the array once and tracks how many times the current value repeats. Because the array is sorted, identical values form a continuous segment. You increment a counter while elements are equal and reset it when the value changes. The moment the counter exceeds n / 4, that element must be the answer. This approach uses only a few variables and performs a single pass over the array, making it extremely reliable and easy to implement.
The key insight is that sorted order removes the need for a hash map or extra storage. Instead of storing frequencies, you simply count consecutive elements. This is the most practical approach in production code because it is straightforward and runs in linear time.
Approach 2: Binary Search Approach (O(log n) per check, O(1) space)
The sorted property allows a more algorithmic solution using binary search. If an element appears more than 25% of the time, then one of the indices n/4, n/2, or 3n/4 must lie inside its occurrence range. These indices become candidate values. For each candidate, perform binary search to find its first occurrence and verify whether the element at index + n/4 is the same value.
This works because an element that appears more than n/4 times must span at least n/4 + 1 consecutive indices. Binary search quickly locates the left boundary of the candidate, and a constant-time index check confirms whether the frequency threshold is satisfied.
Recommended for interviews: Start with the linear scan approach. It shows you recognize that sorted arrays allow frequency counting with a single pass and constant space. Once that works, discuss the binary search optimization that checks specific positions (n/4, n/2, 3n/4). Interviewers usually expect the linear scan implementation but appreciate the binary search insight because it demonstrates deeper understanding of sorted-array properties.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Best default approach when the array is sorted and you want the simplest implementation. |
| Binary Search Candidate Check | O(log n) | O(1) | Useful when leveraging sorted structure and practicing boundary searches with binary search. |