Element Appearing More Than 25% In Sorted Array

Difficulty: Easy | Acceptance: 61.20% | Paid: No Topics: Array

Given an integer array sorted in non-decreasing order, return the element that appears more than 25% of the time in this array.

• Examples
• Constraints
• Hash Map Frequency Count
• Linear Scan
• Fixed Window Check
• Binary Search on Candidates

Examples

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^4
- 0 <= arr[i] <= 10^5

Hash Map Frequency Count

Intuition We can iterate through the array and count the frequency of every element using a hash map. Since we only need to find the element that appears more than 25% of the time, we can check the counts against the threshold n / 4.

Steps

• Calculate the threshold quarter as n / 4.
• Initialize a hash map to store frequencies.
• Iterate through the array, incrementing the count for each element.
• Iterate through the map entries and return the key where the value exceeds quarter.

from typing import List
from collections import Counter

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        quarter = n // 4
        count = Counter(arr)
        for k, v in count.items():
            if v > quarter:
                return k
        return -1

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space proportional to the number of unique elements.

Linear Scan

Intuition Since the array is sorted, identical elements are grouped together. We can iterate through the array and count the length of the current consecutive sequence. If the count exceeds n / 4, we return that element immediately.

Steps

• Calculate n and quarter.
• Initialize count to 1.
• Iterate from index 1 to the end of the array.
• If arr[i] equals arr[i-1], increment count. Otherwise, reset count to 1.
• If count exceeds quarter, return arr[i].
• Return the last element as a fallback (handles cases where the target is at the very end).

from typing import List

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        quarter = n // 4
        count = 1
        for i in range(1, n):
            if arr[i] == arr[i - 1]:
                count += 1
            else:
                count = 1
            if count > quarter:
                return arr[i]
        return arr[-1]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal space usage, leveraging the sorted property.

Fixed Window Check

Intuition If an element appears more than 25% of the time in a sorted array of length n, then that element must occupy at least one position in the first 75% of the array and also appear at the position n / 4 steps ahead. Specifically, for any index i, if arr[i] == arr[i + n/4], then arr[i] is the answer because the distance between these two indices is n/4, meaning there are at least n/4 + 1 occurrences of that element.

Steps

• Calculate n and span (which is n / 4).
• Iterate i from 0 to n - span - 1.
• Check if arr[i] is equal to arr[i + span].
• If they are equal, return arr[i].

from typing import List

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        span = n // 4
        for i in range(n - span):
            if arr[i] == arr[i + span]:
                return arr[i]
        return -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Very concise and efficient, relying on the mathematical property of the sorted array.

Binary Search on Candidates

Intuition Since the array is sorted, the element appearing more than 25% must occupy one of the “quarter” positions: 0, n/4, n/2, or 3n/4. We can pick these four candidates and use binary search to find the first and last occurrence of each candidate. If the range length (last - first + 1) is greater than n / 4, we return that candidate.

Steps

• Calculate n and quarter.
• Define a helper function findLeft to find the first index of a target using binary search.
• Define a helper function findRight to find the last index of a target using binary search.
• Iterate through the candidate indices: 0, n/4, n/2, 3n/4.
• For each candidate value, find its left and right bounds.
• If right - left + 1 > quarter, return the candidate.

from typing import List
import bisect

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        quarter = n // 4
        candidates = [arr[n // 4], arr[n // 2], arr[3 * n // 4]]
        
        for cand in candidates:
            left = bisect.bisect_left(arr, cand)
            right = bisect.bisect_right(arr, cand) - 1
            if right - left + 1 > quarter:
                return cand
        return arr[0]

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Theoretically the fastest time complexity, though with a small constant factor due to checking multiple candidates.