Element Appearing More Than 25% In Sorted Array - Solution & Explanation
Problem Statement
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] <= 105
Approach Overview
Problem 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 1: Linear Scan Approach
This approach involves scanning the array with a single pass. Given that an element occurring more than 25% will appear as a block, we can count the occurrences of an element until it changes and check the count.
For a given element arr[i], count consecutive occurrences. If it exceeds the threshold (n/4), return that element immediately.
This C program uses a for loop to iterate over the sorted array. Using a threshold of n/4, it checks for consecutive elements, increasing a count until the count exceeds the threshold, returning the element if found.
Complexity
Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space.
Approach 2: Binary Search Approach
This approach involves using binary search to take advantage of the sorted nature of the array. By checking elements at regular intervals (n/4), we can identify any elements that repeat in significant blocks more than the threshold.
Instead of scanning the entire array sequentially, we check index positions at specific intervals (n/4, n/2, 3n/4) to find the repeating element.
This binary search-based approach checks specific, equally distanced indices (n/4 positions) and determines if an element appears more than the 25% threshold by comparing element boundaries within each block.
Complexity
Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1).
Approach 3: Traversal
We traverse the array arr from the beginning. For each element arr[i], we check if arr[i] is equal to arr[i + \left\lfloor \frac{n}{4} \right\rfloor], where n is the length of the array. If they are equal, then arr[i] is the element we are looking for, and we return it directly.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Linear Scan Approach | Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space. |
| Binary Search Approach | Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1). |
| Traversal | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Element Appearing More Than 25% In Sorted Array | 3 Approaches | Leetcode-1287 • codestorywithMIK • 3,295 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Element Appearing More Than 25% In Sorted Array easy or hard?
Element Appearing More Than 25% In Sorted Array Python/Java solution
How to solve Element Appearing More Than 25% In Sorted Array in O(n)?
What is the best approach for Element Appearing More Than 25% In Sorted Array?
Is Element Appearing More Than 25% In Sorted Array asked at Google/Amazon/Meta?
What data structure is used in Element Appearing More Than 25% In Sorted Array?
What is the time complexity of Element Appearing More Than 25% In Sorted Array?
Ready to solve this problem?
Practice Element Appearing More Than 25% In Sorted Array with our built-in code editor and test cases.
Practice on FleetCode