Element Appearing More Than 25% In Sorted Array

Element Appearing More Than 25% In Sorted Array

What is this problem about?

The Element Appearing More Than 25% In Sorted Array coding problem asks you to find an integer in a sorted array that occurs more than 25% of the time. Given that the array is sorted, all occurrences of the same number will be contiguous. The problem guarantees that exactly one such element exists.

Why is this asked in interviews?

Companies like Amazon and Microsoft use this array interview pattern to test whether a candidate can leverage the "sorted" property of an array to optimize a search. While a linear scan (O(N)) is easy, the problem can be solved in O(log N) time using binary search, which demonstrates a higher level of algorithmic thinking.

Algorithmic pattern used

There are two main approaches:

1. Linear Scan (O(N)): Since the array is sorted, you can check if arr[i] == arr[i + span], where span is n / 4. If they are equal, then all elements between them are also the same, meaning the element appears at least span + 1 times.
2. Binary Search (O(log N)): The target element must appear at one of the "quarter" indices: n/4, n/2, or 3n/4. For each of these candidates, use binary search to find its first and last occurrence and calculate the total count.

Example explanation

Array: [1, 2, 2, 6, 6, 6, 6, 7, 10], n = 9.

1. 25% of 9 is 2.25. We need an element appearing at least 3 times.
2. Index span = 9 / 4 = 2.
3. Check arr[i] and arr[i+2]:
   • arr[0]=1, arr[2]=2. Not same.
   • arr[1]=2, arr[3]=6. Not same.
   • arr[2]=2, arr[4]=6. Not same.
   • arr[3]=6, arr[5]=6. Same! Wait, the span should be n/4. For n=9, span=2. arr[3] to arr[5] is a sequence of 6s. arr[3] to arr[6] is four 6s. The element is 6.

Common mistakes candidates make

• Using a Hash Map: Using a frequency map (O(N) space) when the sorted property allows for O(1) space.
• Ignoring the Sorted Property: Not realizing that you only need to check a few specific offsets instead of every element.
• Floating Point Errors: Incorrectly calculating "25%" using float division when integer floor division (n / 4) is safer for index logic.

Interview preparation tip

Whenever you see "Sorted Array" and "Find an element with property X," your mind should immediately jump to Binary Search. Even if O(N) is acceptable, discussing the O(log N) possibility shows you are thinking about scale.