LeetCode 1287 - Element Appearing More Than 25% In Sorted Array

The problem gives us a sorted integer array in non-decreasing order. We are guaranteed that exactly one element appears

leetcodeeasyarray

LeetCode Problem 1287

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us a sorted integer array in non-decreasing order. We are guaranteed that exactly one element appears more than 25% of the time in the array, and we need to return that element.

In other words, among all numbers in the array, there is one value whose frequency is strictly greater than n / 4, where n is the length of the array. Because the array is already sorted, equal values appear together in contiguous blocks. This sorted property is the key observation that allows us to solve the problem efficiently.

The input is:

  • A sorted array arr
  • Length between 1 and 10^4
  • Values between 0 and 10^5

The output is:

  • The single integer that appears more than 25% of the time

The constraints are relatively small, so even an O(n) or O(n log n) solution would easily pass. However, the sorted nature of the input allows us to avoid unnecessary work and produce a very clean solution.

Several edge cases are important to think about early:

  • Arrays of length 1, where the only element must be the answer
  • Arrays where the frequent element appears at the beginning
  • Arrays where the frequent element appears at the end
  • Arrays where the frequent element barely exceeds the 25% threshold
  • Arrays with all identical elements

The problem also guarantees that exactly one valid answer exists, so we never need to handle ambiguity or missing results.

Approaches

Brute Force Approach

A straightforward solution is to count the frequency of every number using a hash map.

We iterate through the array, store counts in a dictionary, and then check which number has frequency greater than n // 4.

This approach works because we explicitly compute the exact frequency of every value. Once frequencies are known, identifying the valid element is trivial.

However, this solution ignores the fact that the array is sorted. It also uses extra memory for the hash map, even though the sorted order already groups equal values together.

Optimal Approach

The key insight comes from the sorted property.

If an element appears more than 25% of the time, then within any block of size n / 4, that element must repeat. More specifically, for some index i, the value at arr[i] must equal the value at arr[i + n/4].

Because identical elements are contiguous in a sorted array, checking this condition is enough to identify the special element.

For example:

arr = [1,2,2,6,6,6,6,7,10]
n = 9
threshold = 9 // 4 = 2

The element 6 appears four times. If we compare:

arr[3] == arr[5]
6 == 6

then we immediately know 6 spans more than threshold positions.

This lets us solve the problem in linear time with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Count frequencies using a hash map
Optimal O(n) O(1) Exploits sorted order and distance checking

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the length of the array, n.
  2. Compute the threshold distance:
threshold = n // 4

If an element appears more than 25% of the time, then there must exist two equal elements separated by at least this distance. 3. Iterate through the array from index 0 to n - threshold - 1.

At each index i, compare:

arr[i] and arr[i + threshold]
  1. If these two values are equal, return that value immediately.

This works because equal values in a sorted array form one continuous block. If the same value appears at positions separated by threshold, then its frequency must exceed 25%. 5. Since the problem guarantees exactly one valid answer, the algorithm will always find and return a result.

Why it works

The correctness relies on the contiguous nature of equal values in a sorted array.

Suppose a value appears more than n / 4 times. Then its block length is strictly greater than threshold = n // 4. Therefore, within that block, there must exist indices i and i + threshold containing the same value.

Conversely, if arr[i] == arr[i + threshold], then that value spans more than threshold positions, meaning it appears more than 25% of the time.

Because the problem guarantees exactly one such element exists, the first match we find is the correct answer.

Python Solution

from typing import List

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        threshold = n // 4

        for i in range(n - threshold):
            if arr[i] == arr[i + threshold]:
                return arr[i]

        return -1

The implementation begins by computing the array length and the threshold value n // 4.

The loop runs only while i + threshold remains inside the array bounds. At each position, we compare the current value with the value threshold positions ahead.

If the two values are equal, then the sorted property guarantees that this value occupies a large enough contiguous range to exceed 25% frequency.

The function immediately returns the matching value because the problem guarantees exactly one valid answer exists.

The final return -1 is technically unnecessary under the problem constraints, but it is included as a safety fallback.

Go Solution

func findSpecialInteger(arr []int) int {
	n := len(arr)
	threshold := n / 4

	for i := 0; i < n-threshold; i++ {
		if arr[i] == arr[i+threshold] {
			return arr[i]
		}
	}

	return -1
}

The Go implementation follows the exact same logic as the Python version.

Slices in Go already provide indexed access similar to arrays, so no additional data structures are needed. Integer division automatically truncates toward zero, which correctly computes n / 4.

Like the Python solution, the final return -1 is only a fallback and should never execute under valid problem constraints.

Worked Examples

Example 1

Input: [1,2,2,6,6,6,6,7,10]

Array length:

n = 9
threshold = 9 // 4 = 2
i arr[i] arr[i + threshold] Equal?
0 1 2 No
1 2 6 No
2 2 6 No
3 6 6 Yes

At index 3, we find:

arr[3] == arr[5]
6 == 6

So we return 6.

Example 2

Input: [1,1]

Array length:

n = 2
threshold = 2 // 4 = 0
i arr[i] arr[i + threshold] Equal?
0 1 1 Yes

We immediately return 1.

Because the threshold is 0, every element matches itself. Since the array contains exactly one valid answer, this still works correctly.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array
Space O(1) Uses only a few variables

The algorithm scans the array once, performing constant-time comparisons at each step. No auxiliary data structures are allocated, so the extra memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        threshold = n // 4

        for i in range(n - threshold):
            if arr[i] == arr[i + threshold]:
                return arr[i]

        return -1

sol = Solution()

assert sol.findSpecialInteger([1,2,2,6,6,6,6,7,10]) == 6  # provided example
assert sol.findSpecialInteger([1,1]) == 1  # small array with duplicate values
assert sol.findSpecialInteger([5]) == 5  # single element array
assert sol.findSpecialInteger([1,2,3,3]) == 3  # element appears exactly 50%
assert sol.findSpecialInteger([2,2,2,3,4,5]) == 2  # frequent element at beginning
assert sol.findSpecialInteger([1,2,3,4,4,4]) == 4  # frequent element at end
assert sol.findSpecialInteger([7,7,7,7]) == 7  # all elements identical
assert sol.findSpecialInteger([1,1,2,3]) == 1  # minimal valid frequency
assert sol.findSpecialInteger([1,2,2,2,3,4,5]) == 2  # frequent middle block
assert sol.findSpecialInteger([0,0,0,1,2,3,4,5]) == 0  # includes zero value
Test Why
[1,2,2,6,6,6,6,7,10] Validates standard example
[1,1] Tests very small array
[5] Tests single-element input
[1,2,3,3] Tests small array with end repetition
[2,2,2,3,4,5] Frequent element at start
[1,2,3,4,4,4] Frequent element at end
[7,7,7,7] All elements identical
[1,1,2,3] Barely exceeds threshold
[1,2,2,2,3,4,5] Frequent element in middle
[0,0,0,1,2,3,4,5] Validates handling of zero values

Edge Cases

One important edge case is a single-element array such as [5]. Since the only element appears 100% of the time, it must be the answer. The implementation handles this naturally because the threshold becomes 0, and the first comparison immediately succeeds.

Another important case is when the frequent element appears at the beginning or end of the array. Some implementations incorrectly assume the frequent block must appear in the middle. For example, [2,2,2,3,4,5] and [1,2,3,4,4,4] both work correctly because the algorithm checks every valid starting index.

A subtle edge case occurs when the threshold becomes zero, which happens for very small arrays such as length 1, 2, or 3. In these situations, the comparison becomes arr[i] == arr[i], which is always true. This is still correct because the problem guarantees exactly one valid answer exists, so returning the first element is valid.

Another important case is when all elements are identical, such as [7,7,7,7]. The algorithm immediately detects equality across the threshold distance and returns the repeated value without needing any special handling.