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

Labels:

Comments

Post a Comment

Popular posts from this blog

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well. I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code. A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front. There are two types of heaps: Min Heap: The smallest item is at the front. It's like standing in a line where the shortest person is always at the front. Max Heap: The largest item is at the front. It's like stand...
2 comments
Read more

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...
Post a Comment
Read more

2125. Number of Laser Beams in a Bank

Hi Guys, Today is 3 January 2024 and below is the solution for problem of the day So, the question we have is Number of Laser Beams in a Bank .  In this we have to find total number of lasers. So just imagine it as we have to find number of lines connecting the dots.  so if there are 2 dots. we will have one line, if we have 3 dots we will get 3 lines, and so on... Now relate the above provided example, let's relate this to our problem statement.   We have 4 walls, first wall has 3 lasers, second wall has 0 lasers, third wall got 2 lasers and last wall has 1 laser. So as i suggested we need to connect dots so make sure to only join adjacent dots. So lasers from 1 and 3 wall  will connect to each other (6 lasers) and wall 3 and 4 will connect to each other (2 lasers). So total of 8 lasers, which is the required output anyways. class Solution : def numberOfBeams ( self , bank : List[ str ]) -> int : val = 0 # Initialize a variable `val` to store th...
Post a Comment
Read more