# Element Appearing More Than 25% In Sorted Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/element-appearing-more-than-25percent-in-sorted-array
**Data structures:** Array
---
## Problem
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 <= 104`
* `0 <= arr[i] <= 105`

# Approaches
## Frequency Counting with Hash Map
This approach involves iterating through the array and using a hash map to store the frequency of each element. It's a straightforward method that would also work for an unsorted array, but it doesn't leverage the key information that the input array is sorted.
**Time:** O(N), where N is the number of elements in the array. We iterate through the array at most once. · **Space:** O(K), where K is the number of unique elements in the array. In the worst-case scenario where all elements are unique, the space complexity becomes O(N).
**Pros:** Simple to understand and implement.; It is a general-purpose solution for finding frequent elements and works even if the array is not sorted.
**Cons:** Does not utilize the sorted property of the array, making it less efficient than possible.; Requires extra space for the hash map, which can be significant if the number of unique elements is large.
### Explanation
The core idea is to count the occurrences of every number and identify which one appears more than 25% of the time. We can use a `HashMap` (or a dictionary in other languages) to map each number to its frequency.

We first calculate the threshold value, `threshold = n / 4`, where `n` is the length of the array. Then, we iterate through the array. For each number, we update its count in the hash map. Immediately after updating, we check if the count has surpassed the `threshold`. If it has, we have found our special integer and can return it right away, without needing to process the rest of the array. The problem statement guarantees that exactly one such integer exists, so this check will eventually succeed.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int threshold = n / 4;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > threshold) {
                return num;
            }
        }
        return -1; // Should not be reached based on problem description
    }
}
```
### Algorithm
- Calculate the threshold count required, which is `arr.length / 4`.
- Initialize a hash map to store the frequency of each number in the array.
- Iterate through the input array `arr` from left to right.
- For each element, increment its count in the hash map.
- After updating the count for an element, check if its new count is greater than the calculated threshold.
- If it is, that element is the answer, and we can return it immediately.
- Since the problem guarantees that such an element always exists, the function will always return a value from within the loop.

## Linear Scan
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Calculate the quarter length: `quarter = n / 4`.
- Iterate through the array with an index `i` from `0` up to `n - quarter - 1`.
- In each iteration, compare the element at the current index, `arr[i]`, with the element at index `i + quarter`.
- If `arr[i] == arr[i + quarter]`, it means the element `arr[i]` spans a distance of at least `quarter` indices. This implies it appears at least `quarter + 1` times, 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.

## Binary Search on Candidate Elements
This is the most optimal approach, which fully exploits the sorted property and the 'more than 25%' condition. The core idea is that if an element appears more than a quarter of the time, it must be present at certain key indices in the array. By checking only these few candidates, we can find the answer in logarithmic time.
**Time:** O(log N), where N is the length of the array. We identify a constant number of candidates (3), and for each, we perform two binary searches to find its frequency. Each binary search takes O(log N) time. · **Space:** O(1), as no extra space proportional to the input size is needed. The binary search is done in-place.
**Pros:** Extremely efficient with a time complexity of O(log N), making it the optimal solution.; Uses constant O(1) extra space.
**Cons:** The logic is more subtle and relies heavily on the specific problem statement (sorted array and >25% frequency).; Implementation is more complex due to the need for binary search helper functions to find the first and last occurrences of an element.
### Explanation
Given that the array is sorted and one element appears more than `n/4` times, this block of identical elements must be long enough to cross one of the quarter-marks of the array. Imagine dividing the array into four segments. A block of length `> n/4` cannot fit entirely between the quarter-marks. Therefore, the special element must be one of `arr[n/4]`, `arr[n/2]`, or `arr[3*n/4]`.

This reduces the problem to checking just these three candidates. For each candidate, we need to find its actual frequency in the array. Since the array is sorted, we can do this very efficiently using binary search. We find the first (leftmost) and last (rightmost) index of the candidate element. The total count is then `last_index - first_index + 1`. If this count is greater than `n/4`, we have found our answer.

```java
class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        if (n == 1) return arr[0];
        int threshold = n / 4;
        
        int[] candidateIndices = {n / 4, n / 2, 3 * n / 4};
        
        for (int index : candidateIndices) {
            int candidate = arr[index];
            int first = findFirst(arr, candidate);
            int last = findLast(arr, candidate);
            if (last - first + 1 > threshold) {
                return candidate;
            }
        }
        
        return -1; // Should not be reached
    }

    // Binary search to find the first occurrence of a target
    private int findFirst(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int firstIndex = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                firstIndex = mid;
                high = mid - 1; // Look for earlier occurrences
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return firstIndex;
    }

    // Binary search to find the last occurrence of a target
    private int findLast(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int lastIndex = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                lastIndex = mid;
                low = mid + 1; // Look for later occurrences
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return lastIndex;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Identify three candidate elements. Because the special element occurs more than 25% of the time, its contiguous block in the sorted array must overlap with at least one of the quarter-points of the array. The candidates are the elements at indices `n/4`, `n/2`, and `3n/4`.
- For each of the three candidate elements:
  - Use a binary search helper function to find the index of its first occurrence (lower bound).
  - Use another binary search helper function to find the index of its last occurrence (upper bound).
  - Calculate the total count of the candidate: `count = last_index - first_index + 1`.
  - Check if `count` is greater than `n / 4`.
  - If it is, this candidate is the special integer, and we return it.

# Solutions
### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @param {number[]} arr * @return {number} */ var findSpecialInteger =
  function (arr) {
    const n = arr.length;
    for (let i = 0; i < n; ++i) {
      if (arr[i] == arr[i + (n >> 2)]) {
        return arr[i];
      }
    }
    return 0;
  };

```

### CPP

```cpp
class Solution { public: int findSpecialInteger ( vector < int >& arr ) { int n = arr . size (); for ( int i = 0 ; i < n ; ++ i ) if ( arr [ i ] == arr [ i + ( n >> 2 )]) return arr [ i ]; return 0 ; } };
```

### Python

```python
class Solution : def findSpecialInteger ( self , arr : List [ int ]) -> int : n = len ( arr ) for i , val in enumerate ( arr ): if val == arr [ i + ( n >> 2 )]: return val return 0
```