Find Number with More Than 25 Percent Frequency In Sorted Array

Leetcode

  1. Element Appearing More Than 25% In Sorted Array
class Solution(object):
    def findSpecialInteger(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        if len(arr) > 8:
            return self.getMostFrequentNumberOptimized(arr)
        
        return self.getMostFrequentNumber(arr)
    
    def getMostFrequentNumber(self, arr):
        counter = {}
        
        for n in arr:
            if n in counter:
                counter[n] += 1
            else:
                counter[n] = 1
                
        targetPercent = (len(arr) * 25)//100
        
        for n in counter:
            if counter[n] > targetPercent:
                return n
            
    def getMostFrequentNumberOptimized(self, arr):
        numsCount = len(arr)
        p1 = (numsCount // 4) - 1
        p2 = (numsCount // 2) - 1
        p3 = ((numsCount * 3) // 4) - 1
        
        print("len=", numsCount, "p1=", p1, "p2=", p2, "p3=", p3)
        print(arr[0], arr[p1], arr[p2], arr[p3], arr[-1])
        
        if arr[0] == arr[p1]:
            return arr[0]
        
        if arr[p1] == arr[p2]:
            return arr[p1]
        
        if arr[p2] == arr[p3]:
            return arr[p2]
        
        if arr[p3] == arr[-1]:
            return arr[p3]

The above optimized approach has a flaw. The offsets are fixed and the 25% spread can be across two quartets.

num = [1,2,2,2,3,4,4,5,6,6,7,7]

We need to use a sliding window of quarters.

def getMostFrequentNumberOptimized(self, arr):
        n = len(arr)
        offset = n/4
        
        for i in range(n - offset):
            if arr[i] == arr[i + offset]:
                return arr[i]

Reference

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: