LeetCode Entry

1095. Find in Mountain Array

12.10.2023 hard 2023 kotlin

Binary Search in a mountain

1095. Find in Mountain Array hard blog post substack image.png

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 and hi
  • 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
    }