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] <= 105The key observation in #1287 Element Appearing More Than 25% In Sorted Array is that the array is already sorted. If an element appears more than 25% of the time, its occurrences must span at least n/4 consecutive positions in the array. This property allows us to avoid counting every frequency explicitly.
A common strategy is to check specific candidate indices such as n/4, n/2, and 3n/4. For each candidate value, we verify whether the element at position i and i + n/4 are the same. If they match, that element must appear more than 25% of the time. Because the array is sorted, equal values are grouped together, making this verification efficient.
An alternative approach is to perform a simple frequency count while scanning the array, but the index-check method leverages the sorted structure for a cleaner solution. The optimized approach runs in O(n) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Index gap check using sorted property | O(n) | O(1) |
| Linear scan with frequency counting | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Divide the array in four parts [1 - 25%] [25 - 50 %] [50 - 75 %] [75% - 100%]
The answer should be in one of the ends of the intervals.
In order to check which is element is the answer we can count the frequency with binarySearch.
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.
Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int findSpecialInteger(vector<int>& arr) {
6 int n = arr.size();
7 int count = 1;
8 for (int i = 1; i < n; i++) {
9 if (arr[i] == arr[i-1]) {
10 count++;
11 if (count > n / 4) return arr[i];
12 } else {
13 count = 1;
14 }
}
return arr[0];
}
int main() {
vector<int> arr = {1,2,2,6,6,6,6,7,10};
cout << findSpecialInteger(arr) << endl;
return 0;
}This is a simple implementation of iterating through a vector, counting occurrences of the current element. If the count exceeds n/4, it returns the current element as the answer. As the array is sorted, this algorithm efficiently counts occurrences.
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.
Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Since the array is sorted, identical values appear in consecutive positions. If an element occurs more than 25% of the time, it must cover at least n/4 consecutive indices, making it possible to detect using index comparisons rather than full counting.
Problems like this are common in coding interviews because they test pattern recognition and the ability to use array properties effectively. While the exact question may vary, similar frequency and sorted-array problems often appear in technical interviews.
No special data structure is required for the optimal solution. The sorted array itself provides enough structure to detect the frequent element using simple index checks and comparisons.
The optimal approach uses the sorted nature of the array. By checking elements at positions like n/4, n/2, and 3n/4 and verifying whether the same value appears n/4 positions ahead, we can quickly detect the element that occurs more than 25%. This avoids maintaining explicit frequency counts.
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.