Element Appearing More Than 25% In Sorted Array

Here’s a way to approach the problem by iterating through the sorted array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        count = 1

        for i in range(1, n):
            # If the current element is the same as the previous one, increment the count
            if arr[i] == arr[i - 1]:
                count += 1
            else:
                # If the count of the previous element is greater than 25%, return it
                if count / n > 0.25:
                    return arr[i - 1]
                count = 1

        # If the count of the last element is greater than 25%, return it
        if count / n > 0.25:
            return arr[-1]

The solution iterates through the array, keeping track of the count of consecutive identical integers. When the count of a particular integer is greater than 25% of the array’s length, that integer is returned. Since the array is sorted in non-decreasing order, we can simply compare each element with the previous one to decide whether to increment the count or reset it. The solution takes care of the case where the last integer has a count greater than 25% as well.