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.
1public class Main {
2 public static int findSpecialInteger(int[] arr) {
3 int n = arr.length;
4 int
This Java solution follows the same technique, iterating over the array, counting the number of times the same integer appears consecutively. Once it crosses n/4, it returns the integer.
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.
The Python code efficiently uses arithmetic to compare elements at calculated pivot points (n/4 intervals), verifying sequences that presumably cross these thresholds and return the element as the answer.