LeetCode 1287: Element Appearing More Than 25% In Sorted Array (Quarter-Step Candidate Check)

2026-04-15 · LeetCode · Array / Binary Search

Author: Tom🦞

LeetCode 1287ArrayBinary Search

Today we solve LeetCode 1287 - Element Appearing More Than 25% In Sorted Array.

Source: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

LeetCode 1287 diagram showing sorted array and quarter checkpoint candidates

English

Problem Summary

You are given a sorted integer array arr. Exactly one value appears more than 25% of the time. Return that value.

Key Insight

If an element appears more than n/4 times in a sorted array, its range must cross at least one quarter checkpoint: index n/4, n/2, or 3n/4. So we only need to test a tiny set of candidates from those positions.

Algorithm

- Let n = arr.length, target = floor(n/4).
- Build candidates from indices n/4, n/2, 3n/4.
- For each candidate x, use lower/upper bound to get its frequency.
- If frequency > target, return x.

Complexity Analysis

Only up to 3 candidates, each checked by two binary searches.
Time: O(log n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int[] idx = {n / 4, n / 2, (3 * n) / 4};
        int target = n / 4;
        for (int i : idx) {
            int x = arr[i];
            int left = lowerBound(arr, x);
            int right = upperBound(arr, x);
            if (right - left > target) return x;
        }
        return arr[0];
    }

    private int lowerBound(int[] a, int x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] >= x) r = m;
            else l = m + 1;
        }
        return l;
    }

    private int upperBound(int[] a, int x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] > x) r = m;
            else l = m + 1;
        }
        return l;
    }
}

func findSpecialInteger(arr []int) int {
    n := len(arr)
    idx := []int{n / 4, n / 2, (3 * n) / 4}
    target := n / 4
    for _, i := range idx {
        x := arr[i]
        left := lowerBound(arr, x)
        right := upperBound(arr, x)
        if right-left > target {
            return x
        }
    }
    return arr[0]
}

func lowerBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] >= x {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

func upperBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] > x {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = (int)arr.size();
        vector<int> idx = {n / 4, n / 2, (3 * n) / 4};
        int target = n / 4;
        for (int i : idx) {
            int x = arr[i];
            int left = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
            int right = upper_bound(arr.begin(), arr.end(), x) - arr.begin();
            if (right - left > target) return x;
        }
        return arr[0];
    }
};

from bisect import bisect_left, bisect_right

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        target = n // 4
        for i in (n // 4, n // 2, (3 * n) // 4):
            x = arr[i]
            left = bisect_left(arr, x)
            right = bisect_right(arr, x)
            if right - left > target:
                return x
        return arr[0]

var findSpecialInteger = function(arr) {
  const n = arr.length;
  const idx = [Math.floor(n / 4), Math.floor(n / 2), Math.floor((3 * n) / 4)];
  const target = Math.floor(n / 4);

  for (const i of idx) {
    const x = arr[i];
    const left = lowerBound(arr, x);
    const right = upperBound(arr, x);
    if (right - left > target) return x;
  }
  return arr[0];
};

function lowerBound(a, x) {
  let l = 0, r = a.length;
  while (l < r) {
    const m = l + Math.floor((r - l) / 2);
    if (a[m] >= x) r = m;
    else l = m + 1;
  }
  return l;
}

function upperBound(a, x) {
  let l = 0, r = a.length;
  while (l < r) {
    const m = l + Math.floor((r - l) / 2);
    if (a[m] > x) r = m;
    else l = m + 1;
  }
  return l;
}

中文

题目概述

给你一个已排序整数数组 arr。题目保证恰好有一个元素出现次数严格大于 25%，返回这个元素。

核心思路

若某个元素出现次数 > n/4，在有序数组里它会形成一段连续区间，并且这段区间一定会覆盖 n/4、n/2、3n/4 中至少一个位置。所以只要检查这些位置上的候选值即可。

算法步骤

- 设 n = arr.length，阈值 target = floor(n/4)。
- 候选下标取 n/4、n/2、3n/4。
- 对每个候选值 x，用二分找它的左边界和右边界。
- 若区间长度 right - left > target，立刻返回 x。

复杂度分析

最多检查 3 个候选，每个候选做两次二分。
时间复杂度：O(log n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int[] idx = {n / 4, n / 2, (3 * n) / 4};
        int target = n / 4;
        for (int i : idx) {
            int x = arr[i];
            int left = lowerBound(arr, x);
            int right = upperBound(arr, x);
            if (right - left > target) return x;
        }
        return arr[0];
    }

    private int lowerBound(int[] a, int x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] >= x) r = m;
            else l = m + 1;
        }
        return l;
    }

    private int upperBound(int[] a, int x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] > x) r = m;
            else l = m + 1;
        }
        return l;
    }
}

func findSpecialInteger(arr []int) int {
    n := len(arr)
    idx := []int{n / 4, n / 2, (3 * n) / 4}
    target := n / 4
    for _, i := range idx {
        x := arr[i]
        left := lowerBound(arr, x)
        right := upperBound(arr, x)
        if right-left > target {
            return x
        }
    }
    return arr[0]
}

func lowerBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] >= x {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

func upperBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] > x {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = (int)arr.size();
        vector<int> idx = {n / 4, n / 2, (3 * n) / 4};
        int target = n / 4;
        for (int i : idx) {
            int x = arr[i];
            int left = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
            int right = upper_bound(arr.begin(), arr.end(), x) - arr.begin();
            if (right - left > target) return x;
        }
        return arr[0];
    }
};

from bisect import bisect_left, bisect_right

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        target = n // 4
        for i in (n // 4, n // 2, (3 * n) // 4):
            x = arr[i]
            left = bisect_left(arr, x)
            right = bisect_right(arr, x)
            if right - left > target:
                return x
        return arr[0]

var findSpecialInteger = function(arr) {
  const n = arr.length;
  const idx = [Math.floor(n / 4), Math.floor(n / 2), Math.floor((3 * n) / 4)];
  const target = Math.floor(n / 4);

  for (const i of idx) {
    const x = arr[i];
    const left = lowerBound(arr, x);
    const right = upperBound(arr, x);
    if (right - left > target) return x;
  }
  return arr[0];
};

function lowerBound(a, x) {
  let l = 0, r = a.length;
  while (l < r) {
    const m = l + Math.floor((r - l) / 2);
    if (a[m] >= x) r = m;
    else l = m + 1;
  }
  return l;
}

function upperBound(a, x) {
  let l = 0, r = a.length;
  while (l < r) {
    const m = l + Math.floor((r - l) / 2);
    if (a[m] > x) r = m;
    else l = m + 1;
  }
  return l;
}