Skip to main content

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

Comments

Popular posts from this blog

1456, Maximum Number of Vowels in a Substring of Given Length

Hi, folks today I am here with an interesting coding problem from Leetcode. *To directly go to the question please click here. So I will walk through the solution. It will be a brute force and an optimized way solution. I will be explaining the optimized way solutions in depth. # Intuition For any substring of length k, we need to find how many vowels are there in it and provide the highest count of all counts of vowels in a substring. Test Case 1 Input k = 2 and s='asjdee' Output - 2 Explanation: As for substring of length k=2, in the string 's' we have 'ee' when the length is k and the vowels count is 2 Test Case 2 Input k=3 and s='aasdiisdwe' Output - 2 Explanation - For all the substrings with length k = 3 we have 'aas' and 'dii' with 2 vowels each in it. Brute Force - Looping (twice) - Gives TLE (Not recommended) # Approach Create a hashmap (dictionary) with all the vowels in it. Loop through the string till len(s)-k element of strin...

How to bypass Android pattern lock using CMD.

Many of you have encountered the situation where you forget your phone's pattern lock. This is totally common and we can't deny this. Then after trying all the combinations in mind and losing hope we just choose to reset our phone. But here I am providing you with the solution to this problem. You can just open up your phone following these few steps and without undergoing any trouble of losing your data and wasting your time.  Yes, I am talking about bypassing the pattern lock you used to unlock your phone. This procedure will be done using CMD. CMD, also known as command prompt is an amazing tool provided in Windows OP. You can control your entire computer using CMD which includes copying files from one folder to another, hiding your files, checking details of connected wireless devices and even shutting down your PC. You just need to learn some easy commands. How to bypass Pattern lock on your Android Phone? Before trying to Bypass the pattern lock...

1721 - Swapping Nodes in a Linked List.

Hi, Today we will be solving leetcode qs 1721 - Swapping Nodes in a Linked List. This qs is really simple. We need to swap the nodes placed at k distance from the start and end of the Linked List. So let's suppose you have a Linked List input as follows: 1 -> 2-> 4 -> 5 -> 7 -> 8 -> 10-> 9  and you are given a k = 2, so the output should be 1 -> 10 -> 4 -> 5 -> 7 -> 8 -> 2 -> 9 so how do we achieve it??? Intuition The most brute force solution one can think of is using Array data structure. For that, we will traverse through linked List and store all the elements in the Array, swap the two numbers and again insert it in theLinked List again. Not bad, but let's deal with it, it is not the optimal solution and far from being as an acceptable solution in interviews. So what can we done instead of that??? Let's try to look deep into the working of Linked List first and how do we traverse it. Linked List is a linear data structure that...