Element Appearing More Than 25% In Sorted Array

Easy
1102.

Element Appearing More Than 25% In Sorted Array

Element Appearing More Than 25% In Sorted Array is an easy coding problem on arrays and binary search, asked in Amazon, Google and Meta interviews.

arr is sorted in non-decreasing order, and exactly one value in it occurs more than 25% of the time — that is, its count c satisfies 4 * c > arr.length.

Return that value.

Example 1

Input
arr = [1,2,2,6,6,6,6,7,10]
Output
6
Explanation
6 appears 4 times out of 9, which is more than a quarter.

Example 2

Input
arr = [1,1]
Output
1

Example 3

Input
arr = [4,7,7,7,9]
Output
7

Constraints

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5
  • arr is sorted in non-decreasing order
  • Exactly one value occurs more than 25% of the time
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Element Appearing More Than 25% In Sorted Array — Solution

Element Appearing More Than 25% In Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Element Appearing More Than 25% In Sorted Array is an easy coding problem on arrays and binary search, asked in Amazon, Google and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

arr is sorted in non-decreasing order, and exactly one value in it occurs more than 25% of the time — that is, its count c satisfies 4 * c > arr.length.

Return that value.

Example 1

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
Explanation: 6 appears 4 times out of 9, which is more than a quarter.

Example 2

Input: arr = [1,1]
Output: 1

Example 3

Input: arr = [4,7,7,7,9]
Output: 7

Constraints

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5
  • arr is sorted in non-decreasing order
  • Exactly one value occurs more than 25% of the time

Hints for Element Appearing More Than 25% In Sorted Array

  1. Hint 1

    Equal values sit next to each other because the array is sorted.

  2. Hint 2

    A value occurring more than n / 4 times covers a block longer than n / 4 positions.

  3. Hint 3

    Let step = floor(n / 4). The answer is the first arr[i] with arr[i] == arr[i + step].

How to solve Element Appearing More Than 25% In Sorted Array

In a sorted array a value with more than n / 4 copies forms one contiguous block of length at least floor(n / 4) + 1, so its first element equals the element floor(n / 4) places later.

Approach

  1. Let step = floor(n / 4).
  2. For each i with i + step < n, return arr[i] as soon as arr[i] == arr[i + step].

Why it works

If arr[i] == arr[i + step], sortedness forces all step + 1 positions between them to hold the same value, so that value occurs at least floor(n / 4) + 1 times, which is more than n / 4. Conversely the special value's block is that long, so the scan finds it at the block's first index at the latest. Since only one value qualifies, the first hit is the answer.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • "More than 25%" means 4 * count > n; with n = 8 a value needs 3 copies, not 2.
  • When n < 4, step is 0 and the first element is returned — correct, since then the whole array is one value.
  • Counting with a hash map works but ignores the sortedness the problem gives you.

Reference solution

Python

from typing import List

def findSpecialInteger(arr: List[int]) -> int:
    step = len(arr) // 4
    for i in range(len(arr) - step):
        if arr[i] == arr[i + step]:
            return arr[i]
    return arr[0]

Java

public static int findSpecialInteger(int[] arr) {
    int step = arr.length / 4;
    for (int i = 0; i + step < arr.length; i++) {
        if (arr[i] == arr[i + step]) return arr[i];
    }
    return arr[0];
}

C++

int findSpecialInteger(vector<int>& arr) {
    int n = arr.size(), step = n / 4;
    for (int i = 0; i + step < n; i++) {
        if (arr[i] == arr[i + step]) return arr[i];
    }
    return arr[0];
}

JavaScript

var findSpecialInteger = function(arr) {
    var step = Math.floor(arr.length / 4);
    for (var i = 0; i + step < arr.length; i++) {
        if (arr[i] === arr[i + step]) return arr[i];
    }
    return arr[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search