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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find in Mountain Array

Difficulty: Hard

Problem Description

You are given a mountain array mountainArr, and you need to find the minimum index such that mountainArr.get(index) == target. If the target does not exist, return -1. You can only access the elements through the MountainArray interface, which has methods get(k) and length().

Key Insights

  • A mountain array has a single peak, with elements strictly increasing up to the peak and then strictly decreasing.
  • To efficiently find the target, we can leverage binary search in two phases: first to find the peak, and then to search in both halves of the array.
  • Since the mountain array is accessed through an interface, we need to minimize the number of calls to get().

Space and Time Complexity

Time Complexity: O(log n) for finding the peak and O(log n) for searching in the two halves, leading to O(log n) overall.

Space Complexity: O(1), as we are using a constant amount of space.

Solution

The approach consists of two main steps:

  1. Find the Peak: Use binary search to locate the peak of the mountain array. The peak is the index where the value is greater than its neighbors.
  2. Search for Target: Perform binary search in both the increasing and decreasing parts of the array to find the target.

Data Structures and Algorithms Used

  • Binary Search: For both finding the peak and searching for the target.
  • Array: The mountain array is accessed through the provided interface.

Code Solutions

class MountainArray:
    def get(self, index: int) -> int:
        pass

    def length(self) -> int:
        pass

def findInMountainArray(target: int, mountainArr: 'MountainArray') -> int:
    n = mountainArr.length()
    
    # Step 1: Find the peak
    left, right = 0, n - 1
    while left < right:
        mid = left + (right - left) // 2
        if mountainArr.get(mid) < mountainArr.get(mid + 1):
            left = mid + 1
        else:
            right = mid
    peak = left

    # Step 2: Search in the increasing part
    left, right = 0, peak
    while left <= right:
        mid = left + (right - left) // 2
        mid_val = mountainArr.get(mid)
        if mid_val == target:
            return mid
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1

    # Step 3: Search in the decreasing part
    left, right = peak + 1, n - 1
    while left <= right:
        mid = left + (right - left) // 2
        mid_val = mountainArr.get(mid)
        if mid_val == target:
            return mid
        elif mid_val > target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
← Back to All Questions