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.

Description Hints 3 Solution Video 25:35

1287. Element Appearing More Than 25% In Sorted Array

Q: 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.

Easy61.5% acceptance4 companies

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 <= 10⁴
0 <= arr[i] <= 10⁵

Asked at 4 companies

Google Microsoft Meta Amazon

Topics

Array

Hints open one at a time

Hint 1

Divide the array in four parts [1 - 25%] [25 - 50 %] [50 - 75 %] [75% - 100%]

Hint 2

The answer should be in one of the ends of the intervals.

Hint 3

In order to check which is element is the answer we can count the frequency with binarySearch.

25:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findSpecialInteger(self, arr: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[1,1]

Your code is saved on this device.Solution