Skip to main content

Element Appearing More Than 25% In Sorted Array

Problem statement​

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

My solution​

/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function(arr) {
    const countMap = new Map();
    
    for (const num of arr) {
        if (!countMap.has(num)) {
            countMap.set(num, 0)
        }
        
        countMap.set(num, countMap.get(num) + 1)
    }
    
    const threshold = Math.floor(arr.length * 0.25)
    
    for (const [key, value] of countMap.entries()) {
        if (value > threshold) {
            return key
        }
    }
};