Element Appearing More Than 25% In Sorted Array

EASY

Description

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⁵

Approaches

Checkout 3 different approaches to solve Element Appearing More Than 25% In Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Linear Scan

This approach takes advantage of the sorted nature of the array. Since all identical elements are grouped together, we can find the special integer with a single linear scan and without using any extra space.

Algorithm

Get the length of the array, n.
Calculate the quarter length: quarter = n / 4.
Iterate through the array with an index i from 0 up to n - quarter - 1.
In each iteration, compare the element at the current index, arr[i], with the element at index i + quarter.
If arr[i] == arr[i + quarter], it means the element arr[i] spans a distance of at least quarter indices. This implies it appears at least quarter + 1 times, which is more than 25% of the array's length. Therefore, arr[i] is the special integer, and we return it.
The loop is guaranteed to find the answer because the problem states one exists.

If an element appears more than n / 4 times, let's say k times where k > n / 4, then in the sorted array, these k elements will form a contiguous block. The length of this block is k. This means that if we pick the first element of this block at index i, the element at index i + n/4 must be the same, because the block is long enough to cover that distance.

Based on this observation, we can simply iterate through the array and for each element arr[i], check if it's equal to arr[i + n/4]. The first time this condition is met, we have found our answer. We only need to iterate up to n - (n/4) - 1 because i + n/4 must be a valid index.

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int quarter = n / 4;
        for (int i = 0; i < n - quarter; i++) {
            if (arr[i] == arr[i + quarter]) {
                return arr[i];
            }
        }
        return arr[0]; // Fallback for small arrays, e.g., n=1
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the array. In the worst case, we might iterate up to `3/4` of the array.Space Complexity: O(1), as we only use a few variables to store state, regardless of the input size.

Pros and Cons

Pros:

Very efficient in terms of space, using only O(1) extra space.
Simple to implement with a single loop.
Improves upon the hash map approach by eliminating the need for extra storage.

Cons:

The time complexity is still linear, which is not the most optimal solution possible for this specific problem.

Code Solutions

Checking out 4 solutions in different languages for Element Appearing More Than 25% In Sorted Array. Click on different languages to view the code.

class Solution { public int findSpecialInteger ( int [] arr ) { int n = arr . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( arr [ i ] == arr [ i + ( n >> 2 )]) { return arr [ i ]; } } return 0 ; } }

Video Solution

Watch the video walkthrough for Element Appearing More Than 25% In Sorted Array

Data Structures:

Array