How hard is LeetCode 1287. Element Appearing More Than 25% In Sorted Array?

LeetCode 1287. Element Appearing More Than 25% In Sorted Array is rated Easy on LeetCode.

What is the time complexity of LeetCode 1287. Element Appearing More Than 25% In Sorted Array?

The Python solution on this page runs in O(n), where n is the length of the array \textit{arr}.

What is the space complexity of LeetCode 1287. Element Appearing More Than 25% In Sorted Array?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1287. Element Appearing More Than 25% In Sorted Array cover?

LeetCode 1287. Element Appearing More Than 25% In Sorted Array is tagged Array on LeetCode.

Element Appearing More Than 25% In Sorted Array — LeetCode 1287 Python Solution

EasyArray

Problem: #1287
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        for i, x in enumerate(arr):
            if x == arr[(i + (n >> 2))]:
                return x

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array \textit{arr}
Space	O(1) auxiliary

Frequently asked questions

How hard is LeetCode 1287. Element Appearing More Than 25% In Sorted Array?: LeetCode 1287. Element Appearing More Than 25% In Sorted Array is rated Easy on LeetCode.
What is the time complexity of LeetCode 1287. Element Appearing More Than 25% In Sorted Array?: The Python solution on this page runs in O(n), where n is the length of the array \textit{arr}.
What is the space complexity of LeetCode 1287. Element Appearing More Than 25% In Sorted Array?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1287. Element Appearing More Than 25% In Sorted Array cover?: LeetCode 1287. Element Appearing More Than 25% In Sorted Array is tagged Array on LeetCode.