1287. Element Appearing More Than 25% In Sorted Array

Hi, Today i bring you new Leetcode problem. Its an easy one :)

The problem is - Element Appearing More Than 25% In Sorted Array

As qs. explains itself we need to find a number that appears 25% times or more than the length of he array. So for example if array has length of 8 then the resultant number should appear 2 or more times.

The constraints given are- 1 <= arr.length <= 100, 0 <= arr[i] <= 105

So, lets look at the cases which we may encounter.


1. if length is 1. then the number itself is the result.

2. if length is divisibe by 4

3. if length is not divisible by 4.

Let's look at the code now...

 class Solution:

def findSpecialInteger(self, arr: List[int]) -> int:

n = len(arr)

start = 0

end = n

hm = defaultdict()

for i in arr:

hm[i] = hm.get(i, 0)+1

for i in hm:

if hm[i]>n//4:

return i

Now we will go through the code.

Step 1: Initialization

n = len(arr)
start = 0
end = n
hm = defaultdict()

• n is the length of the input list arr.
• start and end are initialized but not used in the provided code snippet.
• hm is a dictionary that will be used to count the occurrences of elements in the list. It's created using defaultdict(), meaning that if a key is not found, it defaults to a count of 0.

Step 2: Counting Occurrences

for i in arr:
    hm[i] = hm.get(i, 0) + 1

• This loop goes through each element i in the input list arr.
• For each element i, it increments the count of i in the dictionary hm. If i is not already a key in hm, it initializes the count to 1. If i is already a key, the current count is incremented.

Step 3: FindingValue which occurs more than 25%.

for i in hm:
    if hm[i] > n // 4:
        return i

• This loop goes through each key i in the dictionary hm.
• For each key i, it checks if the count of i is greater than a quarter (25%) of the length of the input list (n // 4).
• If the count of any element is greater than a quarter of the length of the input list, the method returns that elemen.

Here how this code performed.

 

Hope you like it. Happy coding