Leetcode 1095. Find in Mountain Array

Problem

Leetcode 1095 - Find in Mountain Array

Example:

Input: mountainArr = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Input: mountainArr = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Approach

There are several limitations in this as it says ‘Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer’. Thus keeping this in mind, we can optimize this by putting seen results into dict.

For searching the target, we can do this by doing 3 binary search.

• Fist Binary Search will be used to find the peak of the mountain
• Second Binary Search will be used to find the target from 0 to peak
• Third Binary Search will be used to find the target from peak+1 to length of MountainArray

Here is the Python code for the solution:

class Solution:
    def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
        n = mountainArr.length()
        peak = 0
        cache = {}
        
        # helper function so we can use .get() less
        def get(i):
            if i not in cache:
                cache[i] = mountainArr.get(i)
            return cache[i]

        # First Binary Search: looking for peak using binary search
        left, right = 1, n-2
        while left <= right:
            mid = (left+right) // 2

            l, m, r = get(mid-1), get(mid), get(mid+1)
            # since these are in increasing order peak must be on the right of left pointer
            if l < m < r:
                left = mid+1
            # since these are in decreasing order peak must be on the left of right pointer
            elif l > m > r:
                right = mid-1
            # found peak
            else:
                break
        peak = mid

        # Second Binary Search: looking for target in 0 to peak
        left, right = 0, peak
        while left <= right:
            mid = (left+right) // 2

            if get(mid) == target:
                return mid
            elif get(mid) < target:
                left = mid+1
            else:
                right = mid-1
        
        # Third Binary Search: looking for target in peak+1 to n-1
        left, right = peak+1, n-1
        while left <= right:
            mid = (left+right) // 2

            if get(mid) == target:
                return mid
            # since this is part is in decreasing order
            elif get(mid) < target:
                right = mid-1
            else:
                left = mid+1
        
        # if all else fails
        return -1

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$