Element Appearing More Than 25% In Sorted Array

Element Appearing More Than 25% In Sorted Array - Problem

Array Easy

Given an integer array arr sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Array length is 8, so 25% is 2 elements. Element 6 appears 4 times, which is more than 25% (4 > 2), so return 6.

Example 2 — Different Majority Element

$ Input: arr = [1,1,2,2,3,3,3,3,3]

› Output: 3

💡 Note: Array length is 9, so 25% is 2.25, meaning we need more than 2 elements. Element 3 appears 5 times (5 > 2.25), so return 3.

Example 3 — Minimum Case

$ Input: arr = [1,1,1,2]

› Output: 1

💡 Note: Array length is 4, so 25% is 1 element. Element 1 appears 3 times (3 > 1), so return 1.

Constraints

1 ≤ arr.length ≤ 10⁴
-10⁶ ≤ arr[i] ≤ 10⁶
arr is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array with one element appearing > 25%

Process

Count occurrences and check threshold

Output

Return the majority element

Key Takeaway

🎯 Key Insight: In a sorted array, the majority element forms consecutive groups, making counting efficient

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that since the array is sorted, we can efficiently count occurrences of each element. The optimal approach uses linear scan to count consecutive groups, achieving O(n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(log n)	O(1)	Check quarter-position candidates using binary search for counting
Frequency Count	O(n)	O(n)	Count occurrences of each element and find the one appearing more than 25%
Linear Scan with Early Exit	O(n)	O(1)	Use sorted property to count consecutive elements efficiently

Binary Search Optimization — Algorithm Steps

Step 1: Check candidates at quarter positions
Step 2: For each candidate, use binary search to count occurrences
Step 3: Return the candidate with count > n/4

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Candidates

Elements at positions n/4, n/2, 3n/4

Binary Search Count

Count occurrences using binary search

Check Threshold

Return candidate with count > n/4

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countOccurrences(int* arr, int n, int target) {
    int left = 0, right = n;
    
    // Find leftmost occurrence
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    int leftBound = left;
    
    // Find rightmost occurrence
    left = 0;
    right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    int rightBound = left;
    
    return rightBound - leftBound;
}

int solution(int* arr, int n) {
    int threshold = n / 4;
    
    // Check candidates at quarter positions
    int candidates[3] = {arr[n/4], arr[n/2], arr[3*n/4]};
    
    for (int i = 0; i < 3; i++) {
        if (countOccurrences(arr, n, candidates[i]) > threshold) {
            return candidates[i];
        }
    }
    
    return arr[0]; // fallback
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[1000];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && n < 1000) {
            arr[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Check at most 3 candidates, each requiring O(log n) binary search to count occurrences

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra variables for binary search

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler