#1287

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Element Appearing More Than 25% In Sorted Array

Identify the integer occurring more than 25% in a sorted array using a precise array-driven search strategy for efficiency.

array

Problem Statement

Given a non-decreasing sorted integer array, exactly one element appears in more than 25% of the array. Your task is to return that element efficiently.

For example, in an array [1,2,2,6,6,6,6,7,10], the integer 6 occurs more than 25% of the time. Similarly, in [1,1], the integer 1 satisfies the condition. Arrays will always meet the constraints 1 <= arr.length <= 104 and 0 <= arr[i] <= 105.

Examples

Example 1

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

Output: 6

Example details omitted.

Example 2

Input: arr = [1,1]

Output: 1

Example details omitted.

Constraints

1 <= arr.length <= 104
0 <= arr[i] <= 105

Solution Approach

Quarter Index Candidate Check

Divide the array into four equal segments and examine elements at indices n/4, n/2, and 3n/4. Since the repeating element occupies more than 25%, it must appear at one of these key positions, allowing immediate identification without scanning the entire array.

Count Verification

Once a candidate is selected from quarter positions, count its occurrences by scanning adjacent positions. The first candidate exceeding n/4 confirms the answer, leveraging the sorted property to skip irrelevant sections efficiently.

Optimized Single Pass

Combine candidate selection and verification by comparing element values at quarter indices with their neighbors. This ensures O(log n) time and O(1) space usage, avoiding full linear scans and unnecessary temporary storage.

Complexity Analysis

Metric	Value
Time	O(\log{}n)
Space	O(1)

Time complexity is O(log n) because we only check a constant number of quarter positions rather than the whole array. Space complexity is O(1) as no extra data structures are used beyond index variables.

What Interviewers Usually Probe

Candidates at quarter indices often reveal the element exceeding 25% frequency.
Sorting guarantees that any valid element will span multiple quarter boundaries.
Linear scans across all indices are unnecessary and may indicate inefficiency.

Common Pitfalls or Variants

Common pitfalls

Failing to use sorted property and checking all elements linearly instead of quarter indices.
Miscounting occurrences when the repeating element is near segment boundaries.
Assuming multiple elements could exceed 25% instead of leveraging the problem's unique element guarantee.

Follow-up variants

Find an element appearing more than 33% in a sorted array, adjusting index checks accordingly.
Handle arrays where multiple elements appear frequently but only one exceeds 25%, ensuring correctness.
Apply similar quarter-based search for strings in a sorted list to find the dominant string.

FAQ

What is the best approach for Element Appearing More Than 25% In Sorted Array?

Focus on the array's sorted property, check elements at quarter indices, and verify counts, avoiding full linear scans.

Why does checking quarter indices work for this problem?

Any element appearing more than 25% must cross at least one quarter boundary, making these indices guaranteed candidates.

Can we use extra data structures like hash maps?

While possible, they are unnecessary. The sorted array allows O(1) space solutions using index-based checks.

What if the array is very small?

For arrays smaller than 4 elements, directly compare counts of each element since quarter indices may overlap.

Does this approach generalize to different thresholds?

Yes, adjust the segment divisions according to the target frequency, e.g., thirds for >33%, ensuring candidates fall within boundary indices.

terminal

Solution

Solution 1: Traversal

We traverse the array $\textit{arr}$ from the beginning. For each element $\textit{arr}[i]$, we check if $\textit{arr}[i]$ is equal to $\textit{arr}[i + \left\lfloor \frac{n}{4} \right\rfloor]$, where $n$ is the length of the array. If they are equal, then $\textit{arr}[i]$ is the element we are looking for, and we return it directly.

1

2

3

4

5

6

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

Continue Practicing

#1288 remove covered intervals #1289 minimum falling path sum ii #1284 minimum number of flips to convert binary matrix to zero matrix