12.10.2023
1095. Find in Mountain Array hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/367
Problem TLDR
Binary Search in a mountain
Intuition
First, find the top of the slope. Next, do two Binary Searches on the left and on the right slopes
Approach
to find a top search for where the increasing slope ends
For better Binary Search code
use inclusive
lo
andhi
check the last condition
lo == hi
always update the result
top = max(top, mid)
always move the borders
lo = mid + 1
,hi = mid - 1
move border that cuts off the irrelevant part of the array
Complexity
Time complexity:
O(log(n))Space complexity:
O(1)
Code
fun findInMountainArray(target: Int, mountainArr: MountainArray): Int {
var lo = 1
var hi = mountainArr.length() - 1
var top = -1
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (mountainArr.get(mid - 1) < mountainArr.get(mid)) {
top = max(top, mid)
lo = mid + 1
} else hi = mid - 1
}
lo = 0
hi = top
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
val m = mountainArr.get(mid)
if (m == target) return mid
if (m < target) lo = mid + 1 else hi = mid - 1
}
lo = top
hi = mountainArr.length() - 1
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
val m = mountainArr.get(mid)
if (m == target) return mid
if (m < target) hi = mid - 1 else lo = mid + 1
}
return -1
}