<p>Given an integer array <strong>sorted</strong> in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,2,6,6,6,6,7,10]
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,1]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        #exactly one integer in the array that occurs more than 25% of the time,
        # Boyer Moore Majority Vote for O(1) space. Trivial freq count works for O(n) space
        # elements that appear STRICTLY more than n/k times. k=4 here;  but k=1 since it's given that there is only 1 element
        ME = {}
        for num in arr:
            if num not in ME:
                ME[num] = 0
            ME[num] += 1
            #
            if len(ME) > 3:
                for key in ME.copy():
                    ME[key] -= 1
                    if ME[key] == 0:
                        ME.pop(key)
        #ME now contains the only elements that potentially appear more than n//3 times, now verify
        for key in ME:
            ME[key] = 0
        for num in arr:
            if num in ME:
                ME[num] += 1       
        return [x for x in ME if ME[x] > len (arr)//4][0]
17800