We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find in Mountain Array

Number: 1185

Difficulty: Hard

Paid? No

Companies: Google, Bloomberg, Amazon, Apple, Meta

Problem Description

Given a mountain array (an array that increases then decreases with exactly one peak), and an interface to access it (using MountainArray.get(index) and MountainArray.length()), find the minimum index where the target value exists in the array. If the target is not found, return -1.

Key Insights

  • Use binary search to minimize the number of MountainArray.get calls.
  • First, identify the peak (maximum element) using a modified binary search.
  • Once the peak is found, perform two separate binary searches: one on the increasing part (left side) and one on the decreasing part (right side).
  • Return the index from the left side search if found (since we want the minimum index); otherwise, check the right side.
  • Be mindful of the interactive constraint where total number of get calls must be under 100.

Space and Time Complexity

Time Complexity: O(log n) – binary searches are used to identify the peak and target index. Space Complexity: O(1) – only a constant amount of extra memory is used.

Solution

The solution consists of three main steps:

  1. Peak Finding: Use binary search over the mountain array to locate the peak. In each step, compare element at mid and mid+1 to determine if the peak is to the right or left.
  2. Target Search in the Ascending Part: Conduct a standard binary search in the increasing segment (from index 0 to peak). Since the sequence is sorted in ascending order, a regular binary search works.
  3. Target Search in the Descending Part: If the target is not found on the left, perform a binary search on the decreasing segment (from peak+1 to the end) where comparisons are inverted (i.e., larger values come before smaller ones).
  4. Return the index from the left search if found, otherwise if found on the right, return that index. If not found in either part, return -1.

Code Solutions

# Python solution with detailed comments.
class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        # Find the peak of the mountain array using binary search.
        n = mountain_arr.length()
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            # Compare current value with the next value to decide direction.
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak = left  # The index of the peak
        
        # Binary search on the ascending part of the array.
        def binarySearchAsc(low, high):
            while low <= high:
                mid = (low + high) // 2
                value = mountain_arr.get(mid)
                if value == target:
                    return mid
                elif value < target:
                    low = mid + 1
                else:
                    high = mid - 1
            return -1
        
        # Binary search on the descending part of the array.
        def binarySearchDesc(low, high):
            while low <= high:
                mid = (low + high) // 2
                value = mountain_arr.get(mid)
                if value == target:
                    return mid
                elif value > target:
                    low = mid + 1
                else:
                    high = mid - 1
            return -1
        
        # Try searching in the ascending part.
        index = binarySearchAsc(0, peak)
        if index != -1:
            return index
        # Otherwise, search in the descending part.
        return binarySearchDesc(peak + 1, n - 1)
← Back to All Questions