Element Appearing More Than 25% In Sorted Array solution and explanation
Google
9 more videos on this problem
Element Appearing More Than 25% In Sorted Array | 3 Approaches | Leetcode-1287codestorywithMIK · 25:35 · 3K views
LeetCode 1287: Element Appearing More Than 25% In Sorted Array - Interview Prep Ep 42Fisher Coder · 6:27 · 2K views
1287. Element Appearing More Than 25% In Sorted Array | Binary Search | 3 WaysAryan Mittal · 18:55 · 1K views
Leetcode 1287: Element Appearing More Than 25% In Sorted ArrayAlgorithms Casts · 19:49 · 836 views
Element Appearing More Than 25% In Sorted Array - LeetCode #1287 - Python, JavaScript, Java and C++CodingNinja · 15:01 · 678 views
Leetcode | 1287. Element Appearing More Than 25% In Sorted Array | Easy | Java Solution [2 Methods]Developer Docs · 7:11 · 538 views
1287.Element Appearing More Than 25% In Sorted Array || In Java || Easy Way || #leetcodeQuick Learning With Sree · 8:20 · 461 views
Element Appearing More Than 25% In Sorted Array - LeetCode 1287 - PythonAlpha-Code · 16:53 · 152 views
Solving LeetCode 1287 Element Appearing More Than 25 In Sorted Array | Binary Search | GoogleCode Harmony · 18:30 · 140 views
Leetcode solving: 1287 Element Appearing More Than 25% In Sorted ArrayMath Geeks · 1:51 · 116 views
The 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 <= 1040 <= arr[i] <= 105
Approach overview
Problem Overview: Given a sorted integer array, exactly one element appears more than 25% of the time. Your job is to return that element. The sorted order is the key constraint: equal values appear in contiguous blocks, which makes counting and boundary checks efficient.
Approach 1: Linear Scan Approach (O(n) time, O(1) space)
The simplest solution scans the array once and tracks how many times the current value repeats. Because the array is sorted, identical values form a continuous segment. You increment a counter while elements are equal and reset it when the value changes. The moment the counter exceeds n / 4, that element must be the answer. This approach uses only a few variables and performs a single pass over the array, making it extremely reliable and easy to implement.
The key insight is that sorted order removes the need for a hash map or extra storage. Instead of storing frequencies, you simply count consecutive elements. This is the most practical approach in production code because it is straightforward and runs in linear time.
Approach 2: Binary Search Approach (O(log n) per check, O(1) space)
The sorted property allows a more algorithmic solution using binary search. If an element appears more than 25% of the time, then one of the indices n/4, n/2, or 3n/4 must lie inside its occurrence range. These indices become candidate values. For each candidate, perform binary search to find its first occurrence and verify whether the element at index + n/4 is the same value.
This works because an element that appears more than n/4 times must span at least n/4 + 1 consecutive indices. Binary search quickly locates the left boundary of the candidate, and a constant-time index check confirms whether the frequency threshold is satisfied.
Recommended for interviews: Start with the linear scan approach. It shows you recognize that sorted arrays allow frequency counting with a single pass and constant space. Once that works, discuss the binary search optimization that checks specific positions (n/4, n/2, 3n/4). Interviewers usually expect the linear scan implementation but appreciate the binary search insight because it demonstrates deeper understanding of sorted-array properties.
Approach 1: Linear Scan Approach
This approach involves scanning the array with a single pass. Given that an element occurring more than 25% will appear as a block, we can count the occurrences of an element until it changes and check the count.
For a given element arr[i], count consecutive occurrences. If it exceeds the threshold (n/4), return that element immediately.
def findSpecialInteger(arr):
n = len(arr)
count = 1
for i in range(1, n):
if arr[i] == arr[i-1]:
count += 1
if count > n / 4:
return arr[i]
else:
count = 1
return arr[0]
arr = [1,2,2,6,6,6,6,7,10]
print(findSpecialInteger(arr))public class Main {
public static int findSpecialInteger(int[] arr) {
int n = arr.length;
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i-1]) {
count++;
if (count > n / 4) return arr[i];
} else {
count = 1;
}
}
return arr[0];
}
public static void main(String[] args) {
int[] arr = {1,2,2,6,6,6,6,7,10};
System.out.println(findSpecialInteger(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int findSpecialInteger(vector<int>& arr) {
int n = arr.size();
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i-1]) {
count++;
if (count > n / 4) return arr[i];
} else {
count = 1;
}
}
return arr[0];
}
int main() {
vector<int> arr = {1,2,2,6,6,6,6,7,10};
cout << findSpecialInteger(arr) << endl;
return 0;
}function findSpecialInteger(arr) {
const n = arr.length;
let count = 1;
for (let i = 1; i < n; i++) {
if (arr[i] === arr[i-1]) {
count++;
if (count > n / 4) return arr[i];
} else {
count = 1;
}
}
return arr[0];
}
console.log(findSpecialInteger([1,2,2,6,6,6,6,7,10]));#include <stdio.h>
int findSpecialInteger(int* arr, int arrSize) {
int threshold = arrSize / 4;
int count = 1;
for (int i = 1; i < arrSize; i++) {
if (arr[i] == arr[i-1]) {
count++;
if (count > threshold) return arr[i];
} else {
count = 1;
}
}
return arr[0]; // Fallback case
}
int main() {
int arr[] = {1,2,2,6,6,6,6,7,10};
int result = findSpecialInteger(arr, 9);
printf("%d", result);
return 0;
}using System;
class Program {
public static int FindSpecialInteger(int[] arr) {
int n = arr.Length;
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i-1]) {
count++;
if (count > n / 4) return arr[i];
} else {
count = 1;
}
}
return arr[0];
}
static void Main() {
int[] arr = {1,2,2,6,6,6,6,7,10};
Console.WriteLine(FindSpecialInteger(arr));
}
}The Python solution mimics a count-and-compare approach. For each distinct segment in the list, it checks if the count of similar elements exceeds n/4, returning the first element that fulfills the condition.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Binary Search Approach
This approach involves using binary search to take advantage of the sorted nature of the array. By checking elements at regular intervals (n/4), we can identify any elements that repeat in significant blocks more than the threshold.
Instead of scanning the entire array sequentially, we check index positions at specific intervals (n/4, n/2, 3n/4) to find the repeating element.
def findSpecialInteger(arr):
n = len(arr)
pos = n // 4
for i in range(3):
if arr[i * pos] == arr[(i + 1) * pos - 1]:
return arr[i * pos]
return arr[-1]
arr = [1,2,2,6,6,6,6,7,10]
print(findSpecialInteger(arr))public class Main {
public static int findSpecialInteger(int[] arr) {
int n = arr.length;
int len = n / 4;
for (int i = 0; i < 3; i++) {
if (arr[i*len] == arr[(i+1)*len - 1]) {
return arr[i*len];
}
}
return arr[n - 1];
}
public static void main(String[] args) {
int[] arr = {1,2,2,6,6,6,6,7,10};
System.out.println(findSpecialInteger(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int findSpecialInteger(vector<int>& arr) {
int n = arr.size();
int len = n / 4;
for (int i = 0; i < 3; i++) {
if (arr[i * len] == arr[(i+1) * len - 1]) {
return arr[i * len];
}
}
return arr[n - 1];
}
int main() {
vector<int> arr = {1,2,2,6,6,6,6,7,10};
cout << findSpecialInteger(arr) << endl;
return 0;
}function findSpecialInteger(arr) {
const n = arr.length;
const pos = Math.floor(n / 4);
for (let i = 0; i < 3; i++) {
if (arr[i * pos] === arr[(i + 1) * pos - 1]) {
return arr[i * pos];
}
}
return arr[n - 1];
}
console.log(findSpecialInteger([1,2,2,6,6,6,6,7,10]));#include <stdio.h>
int findSpecialInteger(int* arr, int arrSize) {
int pos = arrSize / 4;
for (int i = 0; i < 3; i++) {
if (arr[i * pos] == arr[(i+1) * pos - 1]) {
return arr[i * pos];
}
}
return arr[arrSize - 1]; // Fallback
}
int main() {
int arr[] = {1,2,2,6,6,6,6,7,10};
int result = findSpecialInteger(arr, 9);
printf("%d", result);
return 0;
}using System;
class Program {
public static int FindSpecialInteger(int[] arr) {
int n = arr.Length;
int len = n / 4;
for (int i = 0; i < 3; i++) {
if (arr[i * len] == arr[(i + 1) * len - 1]) {
return arr[i * len];
}
}
return arr[n - 1];
}
static void Main() {
int[] arr = {1,2,2,6,6,6,6,7,10};
Console.WriteLine(FindSpecialInteger(arr));
}
}The Python code efficiently uses arithmetic to compare elements at calculated pivot points (n/4 intervals), verifying sequences that presumably cross these thresholds and return the element as the answer.
Time Complexity: O(1). Space Complexity: O(1).
Approach 3: Traversal
We traverse the array arr from the beginning. For each element arr[i], we check if arr[i] is equal to arr[i + \left\lfloor \frac{n}{4} \right\rfloor], where n is the length of the array. If they are equal, then arr[i] is the element we are looking for, and we return it directly.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
function findSpecialInteger(arr: number[]): number {
const n = arr.length;
for (let i = 0; ; ++i) {
if (arr[i] === arr[i + (n >> 2)]) {
return arr[i];
}
}
}func findSpecialInteger(arr []int) int {
for i := 0; ; i++ {
if arr[i] == arr[i+len(arr)/4] {
return arr[i]
}
}
}class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function findSpecialInteger($arr) {
$n = count($arr);
for ($i = 0; ; ++$i) {
if ($arr[$i] == $arr[$i + ($n >> 2)]) {
return $arr[$i];
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Linear Scan Approach | Time Complexity: O(n). Space Complexity: O(1). |
| Binary Search Approach | Time Complexity: O(1). Space Complexity: O(1). |
| Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Best default approach when the array is sorted and you want the simplest implementation. |
| Binary Search Candidate Check | O(log n) | O(1) | Useful when leveraging sorted structure and practicing boundary searches with binary search. |
Frequently asked questions
Is Element Appearing More Than 25% In Sorted Array easy or hard?
The problem is classified as Easy because the sorted array property simplifies frequency counting. Recognizing that duplicates appear in contiguous segments makes the linear scan solution straightforward with constant space.
Element Appearing More Than 25% In Sorted Array Python/Java solution
Both Python and Java implementations typically use a single loop to count consecutive occurrences or a binary search helper to find the first index of candidate values. The logic remains identical across languages with O(n) time for the linear scan version.
How to solve Element Appearing More Than 25% In Sorted Array in O(n)?
Iterate through the sorted array while counting consecutive equal elements. Whenever the value changes, reset the counter. If the counter becomes greater than n/4 at any point, return that element immediately. Sorted order guarantees that frequent elements appear in a continuous block.
What is the best approach for Element Appearing More Than 25% In Sorted Array?
The linear scan approach is the most practical solution. Because the array is sorted, identical elements appear consecutively, so you can count frequencies in a single pass and return the element once the count exceeds n/4. This runs in O(n) time and O(1) space and is usually what interviewers expect.
Is Element Appearing More Than 25% In Sorted Array asked at Google/Amazon/Meta?
Problems involving frequency detection and sorted array properties appear frequently in interviews at companies like Amazon and Google. While this exact problem may vary, similar questions about majority elements, frequency thresholds, and binary search boundaries are common.
What data structure is used in Element Appearing More Than 25% In Sorted Array?
The problem mainly relies on array traversal and optionally binary search. No additional data structures like hash maps are required because the array is already sorted, allowing frequency detection using simple index comparisons.
What is the time complexity of Element Appearing More Than 25% In Sorted Array?
The standard linear scan solution runs in O(n) time with O(1) extra space. A binary search based solution checks candidate positions (n/4, n/2, 3n/4) and performs boundary searches, giving O(log n) work per candidate with constant space.