1095.find-in-mountain-array.md

1095. Find in Mountain Array

Clarification Questions

• Is the input array a valid mountain array?

Test Cases

Normal Cases

Input: array = [1,2,3,2,1], target = 3
Output: 2

Input: array = [1,2,3,2,1], target = 0
Output: -1

Edge / Corner Cases

• There are multiple targets.

Input: array = [1,2,3,2,1], target = 2
Output: 1, not 3, because we should return the minimum index.

Binary Search

Given a mountain array and there is a limitation on the number of calls to MountainArray.get function, so we have to find the target in the array with O(log n) time complexity, which means we have to use binary search.

We can divide the problem into two parts:

1. Find the peak index.
2. Find the target in the left part (before the peak) and right part (after the peak).

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *     fun get(index: Int): Int {}
 *     fun length(): Int {}
 * }
 */

class Solution {

    private var peakIndex: Int? = null

    fun findInMountainArray(target: Int, mountainArr: MountainArray): Int {
        if (peakIndex == null) {
            peakIndex = searchPeakIndex(mountainArr)
        }
        val searchResult = searchLeft(mountainArr, target, 0, peakIndex!!)
        return if (searchResult != -1) searchResult
        else searchRight(mountainArr, target, peakIndex!!, mountainArr.length() - 1)
    }

    private fun searchPeakIndex(array: MountainArray): Int {
        var left = 1
        var right = array.length() - 2
        while (left <= right) {
            val middle = left + (right - left) / 2
            val middleValue = array.get(middle)
            val previous = array.get(middle - 1)
            val next = array.get(middle + 1)
            if (previous < middleValue && next < middleValue) return middle
            if (previous > middleValue) right = middle - 1
            else left = middle + 1
        }
        return -1
    }

    private fun searchLeft(array: MountainArray, target: Int, start: Int, end: Int): Int {
        var left = start
        var right = end
        while (left <= right) {
            val middle = left + (right - left) / 2
            val middleValue = array.get(middle)
            if (middleValue == target) return middle
            if (middleValue < target) left = middle + 1
            else right = middle - 1
        }
        return -1
    }

    private fun searchRight(array: MountainArray, target: Int, start: Int, end: Int): Int {
        var left = start
        var right = end
        while (left <= right) {
            val middle = left + (right - left) / 2
            val middleValue = array.get(middle)
            if (middleValue == target) return middle
            // The different part from `searchLeft`.x
            if (middleValue > target) left = middle + 1
            else right = middle - 1
        }
        return -1
    }
}

• Time Complexity: O(lg n)
• Space Complexity: O(1)