We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Element Appearing More Than 25% In Sorted Array

Difficulty: Easy

Problem 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.

Key Insights

  • The array is sorted, which allows us to take advantage of the order for efficient searching.
  • The integer that appears more than 25% of the time must occupy at least one-fourth of the array length.
  • We can find this integer by examining the elements at specific intervals since they will be clustered together.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can utilize the fact that the array is sorted. We will check each element at intervals of n/4 (where n is the length of the array) to find the integer that appears more than 25% of the time. Since the array is sorted, if an integer appears more than 25% of the time, it will occupy a contiguous block of the array. We can simply check the element that appears at index n/4 and verify its count.

Code Solutions

def findSpecialInteger(arr):
    n = len(arr)
    threshold = n // 4
    for i in range(n):
        if i + threshold < n and arr[i] == arr[i + threshold]:
            return arr[i]
    return -1  # This line should theoretically never be reached.
← Back to All Questions