algoadvance

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

Example:

• Input: arr = [1,2,2,6,6,6,6,7,10]
• Output: 6

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

---

Clarifying Questions

1. What should be returned if the array is empty?
   • According to the constraints, the array will always contain at least one element.
2. Are there any other constraints or edge cases to consider?
   • Only one element will appear more than 25% of the time in the array.
   • The array is sorted in non-decreasing order.

---

Strategy

Given that the array is sorted:

1. Determine the Threshold Count: The threshold count for an element to appear more than 25% of the time is calculated by len(arr) // 4.
2. Frequency Counting: Iterate through the array to count the frequency of each element. If an element’s frequency exceeds the threshold, return that element immediately.

An effective approach in a sorted array is to leverage the fact that elements will cluster together. Thus:

• Traverse the array, comparing each element to the previous one.
• Keep a count of the current element’s occurrences.
• If the count reaches the threshold + 1, return that element immediately.

This approach ensures a single pass through the array, making it efficient.

---

Code

def findSpecialInteger(arr):
    threshold = len(arr) // 4
    current_element = arr[0]
    count = 1
    
    for i in range(1, len(arr)):
        if arr[i] == current_element:
            count += 1
        else:
            current_element = arr[i]
            count = 1
        
        if count > threshold:
            return current_element
    
    return current_element  # Should never be reached given problem constraints

# Example Test
arr = [1, 2, 2, 6, 6, 6, 6, 7, 10]
print(findSpecialInteger(arr))  # Output: 6

---

Time Complexity

The time complexity of the solution is O(n) where n is the length of the array arr. This is because it involves a single pass through the array to count the frequency of each element.

• Space Complexity: O(1) since we are using a constant amount of extra space regardless of the input size. The variables threshold, current_element, and count are used to maintain state as we iterate through the array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?