Find in Mountain Array - Leetcode 1095 - Python

[@pranav2066]

This has become my routine. Leetcode all day and daily challenge with Neetcode at Night! Thanks for the Videos

[@steeve1]

I think most hards are pretty silly but I liked this one, probably because i'm comfortable with binary search and didn't feel there was some obscure trick that i'm supposed to magically know.

[@rudrakhare1158]

Corrected Code :_ class Solution: def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int: length = mountain_arr.length() # Find the peak of the mountain array l, r = 0, length - 1 while l < r: m = (l + r) // 2 if mountain_arr.get(m) < mountain_arr.get(m + 1): l = m + 1 else: r = m peak = l # Binary search on the increasing part l, r = 0, peak while l target: r = m - 1 else: return m # Binary search on the decreasing part l, r = peak, length - 1 while l target: l = m + 1 # This should be r = m - 1 elif val < target: r = m - 1 # This should be l = m + 1 else: return m return -1

[@angelchen2843]

Quite easy to understandable!!!! ❤❤

[@picnicbros]

I love binary search

[@silent7152]

Bro help me out 1. Use while(l

[@picnicbros]

@@silent7152 I suggest you read "Powerful Ultimate Binary Search Template" (search on google) to never have bug in your binary search again! The template is basically: left, right = min(search_space), max(search_space) while left < right: mid = left + (right - left) // 2 if condition(mid): left = mid + 1 else: right = mid return left where the else here include the exiting condition *as well as* condition when you update the right pointer. If you do that, in the else statement you can safely update the right pointer. Essentially, you *dont* want to have the exiting condition when you update the left pointer! The template also can be rewritten with those points in mind and still work: left, right = min(search_space), max(search_space) while left < right: mid = left + (right - left) // 2 if condition(mid) or exiting_condition(mid): right = mid else: left = mid + 1 return left So, for this problem, here is two method that will return the peak index: Update left pointer in if condition() method: easier since you don't have to find the exiting condition: while l < r: m = l + (r - l) // 2 if mountain_arr.get(m - 1) < mountain_arr.get(m) < mountain_arr.get(m + 1): l = m + 1 else: r = m peak = l Update right pointer in if condition or exiting_condition() method: while l < r: m = l + (r - l) // 2 left, mid, right = mountain_arr.get(m - 1), mountain_arr.get(m), mountain_arr.get(m + 1) if left > mid > right or (mid > left and mid > right) : r = m else: l = m + 1 peak = l Some side note: this template assumes that the item you want to search is in the range you define. If it is not, it will return the next index that it "assume" the item will be. For example: [1 2 3 4 5], if you search 12, it will assume that 12 will be at index 5, which does not exist in the search space, but it is correct given the condition that arr[i] < arr[i + 1] (sorted array) Also, this template return the first occurrence of your target,if your target has duplicate. For example: [1 2 3 3 3 6 7] if you search 3, it will return 2 (the first occurrence) If you want to find the last occurrence, simply search for target + 1 instead. It will then "assume" the item target + 1 will be in the next position of the last occurrence of target: [1 2 3 3 3 6 7] if you search 4 (target 3 + 1), it will return left = 5. Now, index 5 doesn't have 4, but 6, but that's okay, we simply return left - 1 and that's our last occurrence of target 3. I suggest you do Find First and Last Position of Element in Sorted Array and implement these points. Good luck!

[@GuruPrasadShukla]

keep solving mate!

[@dera_ng]

Do you think I over-thought the question? Maybe if i was in a real interview then I could ask the interviewer if there could be multiple peaks. The English structure of the question promoted me to think about it a bit more and then I got hung up on the edge case (if valid) of having multiple peaks. 😢..... If it's a hard question, I was expecting it to be harder than this.

[@rajarshiverma7686]

Thanks for the great solution, can you also mention how to use bisect here as I have seen solution where few people used bisect

[@yfjsdgzjdnfn]

NeetCode please solve Leetcode 8 String to Integer there are many edge cases out there in that problem ,I requesting please do Video on that

[@hikumai289]

This is medium rather than hard. Wish all of you a good day.

[@sumtpathak19]

the reason behind using mountainArray class is to calculate no. of .get not exceed 100

[@adrianengcheeern]

Is there a possibility that m - 1 or m + 1 would go out of range of the list?

[@user-le6ts6ci7h]

You can't do linear search here eventhough the input size is of 10 pow 4 , because you can call the get at max 100 whixh is enforced by the interface, so better way is use binary search and which takes at max