Problem Description
Given a non-decreasing sorted array of integers, there is exactly one integer that appears more than 25% of the time. Your task is to find and return that integer.
Key Insights
- The array is sorted, which allows us to leverage binary search or index-based checks.
- Because the element appears in more than 25% of the array, it must be present at certain fixed indices such as n/4, n/2, or 3n/4.
- A simple observation: the element at index n/4 is guaranteed to be the special element due to the frequency constraint.
Space and Time Complexity
Time Complexity: O(1) if using the direct index check, or O(n) if a counting method is used. Space Complexity: O(1)
Solution
We can take advantage of the fact that the array is sorted and that the special element appears more than 25% of the time. The key observation is that if an element appears more than n/4 times, then regardless of its starting position, it must appear at the index n/4 (using 0-indexing). This is because even if the element's first occurrence is delayed slightly, its frequency forces it to span at least one of the quarter positions of the array. Therefore, the element at index floor(n/4) is our answer. No additional data structures are needed, and the algorithm works in constant time.