Code Implementation

class Solution:
    def findSpecialInteger(self, arr):
        n = len(arr)
        threshold = n // 4
        for i in range(n - threshold):
            if arr[i] == arr[i + threshold]:
                return arr[i]
        return -1
      

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int threshold = n / 4;
        for (int i = 0; i <= n - threshold; ++i) {
            if (arr[i] == arr[i + threshold]) {
                return arr[i];
            }
        }
        return -1;
    }
};
      

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int threshold = n / 4;
        for (int i = 0; i <= n - threshold; i++) {
            if (arr[i] == arr[i + threshold]) {
                return arr[i];
            }
        }
        return -1;
    }
}
      

var findSpecialInteger = function(arr) {
    const n = arr.length;
    const threshold = Math.floor(n / 4);
    for (let i = 0; i <= n - threshold; i++) {
        if (arr[i] === arr[i + threshold]) {
            return arr[i];
        }
    }
    return -1;
};
      

Problem Description

Given a sorted integer array arr, you are to find the element that appears more than 25% of the time in the array. It is guaranteed that there is exactly one such element. You must return this element.

• The array is sorted in non-decreasing order.
• There is only one valid answer.
• You cannot reuse elements; simply find the value that crosses the 25% frequency threshold.
• Constraints: 1 <= arr.length <= 10^4, 0 <= arr[i] <= 10^5

Thought Process

The first idea that comes to mind is to count the frequency of each element in the array and check if it appears more than 25% of the time. This could be done using a hash map or dictionary. However, since the array is sorted, all identical elements are grouped together, which can be leveraged for a more efficient solution.

Instead of counting every element, we realize that, for any element to appear more than 25% in a sorted array, there must be a block of at least n/4 + 1 consecutive elements with the same value. Thus, if we check for each index i whether the element at arr[i] is the same as the element at arr[i + n/4], we can be sure that this element appears more than 25% of the time. This is much more efficient than counting frequencies for every unique value.

Solution Approach

• Let n be the length of the array.
• The threshold for 25% is n // 4 (integer division).
• Iterate through the array from i = 0 to n - threshold.
• For each index i, compare arr[i] and arr[i + threshold].
• If they are equal, this means there are at least threshold + 1 occurrences of arr[i] in a block, so it must be the answer.
• Return this value immediately upon finding it.
• If no such value is found (which should not happen given the constraints), return -1 as a fallback.

This approach is efficient because:

• We only need to check a small set of indices.
• We avoid counting frequencies for all unique elements.
• The sorted property ensures all identical elements are together, so our check is sufficient to guarantee the answer.

Example Walkthrough

Let's walk through an example with arr = [1,2,2,6,6,6,6,7,10].

• n = 9, so threshold = 9 // 4 = 2
• We check for each i from 0 to 6 (n - threshold = 7):
• At i = 0: arr[0] = 1, arr[2] = 2 (not equal)
• At i = 1: arr[1] = 2, arr[3] = 6 (not equal)
• At i = 2: arr[2] = 2, arr[4] = 6 (not equal)
• At i = 3: arr[3] = 6, arr[5] = 6 (equal!)
• Since arr[3] and arr[5] are both 6, and the block from arr[3] to arr[5] is at least 3 elements, which is more than 25% of 9 (which is 2.25), we return 6.

The answer is 6.

Time and Space Complexity

• Brute-force approach: If we counted frequencies with a hash map, it would take O(n) time and O(n) space in the worst case (if all elements are unique).
• Optimized approach (current): We only iterate through the array once, and each check is O(1). Thus, the time complexity is O(n) and the space complexity is O(1) (no extra space used except for variables).

This optimization is possible because the array is sorted, so we don't need to store counts for every element.

Summary

In this problem, we leveraged the fact that the array is sorted and the guarantee of a unique answer to avoid unnecessary counting. By checking blocks of n/4 + 1 elements, we can efficiently find the element that appears more than 25% of the time in a single pass. This approach is both elegant and efficient, making the most of the problem's constraints.