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

Description

https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

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 1:

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

Example 2:

Input: arr = [1,1]
Output: 1

Constraints:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 105

Explanation

Find the element which occurs more than 25 % of len(arr).

Python Solution

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        percent_25_count = len(arr) // 4
                
        counter = {}
                
        for num in arr:            
            counter[num] = counter.get(num, 0) + 1
            
            
        for key, value in counter.items():
            if value > percent_25_count:
                return key
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.