Element Appearing More Than 25% In Sorted Array — Solution
Element Appearing More Than 25% In Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Element Appearing More Than 25% In Sorted Array is an easy coding problem on arrays and binary search, asked in Amazon, Google and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Binary Search
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr is sorted in non-decreasing order, and exactly one value in it occurs more than 25% of the time — that is, its count c satisfies 4 * c > arr.length.
Return that value.
Example 1
Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
Explanation: 6 appears 4 times out of 9, which is more than a quarter.
Example 2
Input: arr = [1,1]
Output: 1
Example 3
Input: arr = [4,7,7,7,9]
Output: 7
Constraints
1 <= arr.length <= 10^40 <= arr[i] <= 10^5arr is sorted in non-decreasing orderExactly one value occurs more than 25% of the time
Hints for Element Appearing More Than 25% In Sorted Array
Hint 1
Equal values sit next to each other because the array is sorted.
Hint 2
A value occurring more than
n / 4times covers a block longer thann / 4positions.Hint 3
Let
step = floor(n / 4). The answer is the firstarr[i]witharr[i] == arr[i + step].
How to solve Element Appearing More Than 25% In Sorted Array
In a sorted array a value with more than n / 4 copies forms one contiguous block of length at least floor(n / 4) + 1, so its first element equals the element floor(n / 4) places later.
Approach
- Let
step = floor(n / 4). - For each
iwithi + step < n, returnarr[i]as soon asarr[i] == arr[i + step].
Why it works
If arr[i] == arr[i + step], sortedness forces all step + 1 positions between them to hold the same value, so that value occurs at least floor(n / 4) + 1 times, which is more than n / 4. Conversely the special value's block is that long, so the scan finds it at the block's first index at the latest. Since only one value qualifies, the first hit is the answer.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- "More than 25%" means
4 * count > n; withn = 8a value needs 3 copies, not 2. - When
n < 4,stepis 0 and the first element is returned — correct, since then the whole array is one value. - Counting with a hash map works but ignores the sortedness the problem gives you.
Reference solution
Python
from typing import List
def findSpecialInteger(arr: List[int]) -> int:
step = len(arr) // 4
for i in range(len(arr) - step):
if arr[i] == arr[i + step]:
return arr[i]
return arr[0]Java
public static int findSpecialInteger(int[] arr) {
int step = arr.length / 4;
for (int i = 0; i + step < arr.length; i++) {
if (arr[i] == arr[i + step]) return arr[i];
}
return arr[0];
}C++
int findSpecialInteger(vector<int>& arr) {
int n = arr.size(), step = n / 4;
for (int i = 0; i + step < n; i++) {
if (arr[i] == arr[i + step]) return arr[i];
}
return arr[0];
}JavaScript
var findSpecialInteger = function(arr) {
var step = Math.floor(arr.length / 4);
for (var i = 0; i + step < arr.length; i++) {
if (arr[i] === arr[i + step]) return arr[i];
}
return arr[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search