Element Appearing More Than 25% In Sorted Array
EasyPrompt
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: 6Example 2:
Input: arr = [1,1]
Output: 1
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach takes advantage of the sorted nature of the array. Since all identical elements are grouped together, we can find the special integer with a single linear scan and without using any extra space.
Algorithm
- Get the length of the array,
n. - Calculate the quarter length:
quarter = n / 4. - Iterate through the array with an index
ifrom0up ton - quarter - 1. - In each iteration, compare the element at the current index,
arr[i], with the element at indexi + quarter. - If
arr[i] == arr[i + quarter], it means the elementarr[i]spans a distance of at leastquarterindices. This implies it appears at leastquarter + 1times, which is more than 25% of the array's length. Therefore,arr[i]is the special integer, and we return it. - The loop is guaranteed to find the answer because the problem states one exists.
Walkthrough
If an element appears more than n / 4 times, let's say k times where k > n / 4, then in the sorted array, these k elements will form a contiguous block. The length of this block is k. This means that if we pick the first element of this block at index i, the element at index i + n/4 must be the same, because the block is long enough to cover that distance.
Based on this observation, we can simply iterate through the array and for each element arr[i], check if it's equal to arr[i + n/4]. The first time this condition is met, we have found our answer. We only need to iterate up to n - (n/4) - 1 because i + n/4 must be a valid index.
class Solution { public int findSpecialInteger(int[] arr) { int n = arr.length; int quarter = n / 4; for (int i = 0; i < n - quarter; i++) { if (arr[i] == arr[i + quarter]) { return arr[i]; } } return arr[0]; // Fallback for small arrays, e.g., n=1 }}Complexity
Time
O(N), where N is the length of the array. In the worst case, we might iterate up to `3/4` of the array.
Space
O(1), as we only use a few variables to store state, regardless of the input size.
Trade-offs
Pros
Very efficient in terms of space, using only O(1) extra space.
Simple to implement with a single loop.
Improves upon the hash map approach by eliminating the need for extra storage.
Cons
The time complexity is still linear, which is not the most optimal solution possible for this specific problem.
Solutions
Solution
class Solution { public int findSpecialInteger ( int [] arr ) { int n = arr . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( arr [ i ] == arr [ i + ( n >> 2 )]) { return arr [ i ]; } } return 0 ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.