#1095

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find in Mountain Array

Find in Mountain Array requires locating a target using binary search over a peak-structured array efficiently in interactive constraints.

array binary search interactive

Problem Statement

You are given a mountain array, which increases strictly to a single peak and then decreases strictly. Implement an algorithm that interacts with this array to find a specific target value.

Return the smallest index where the target appears using the mountain array interface. If the target is not present, return -1. Each access must respect interactive constraints and minimize calls.

Examples

Example 1

Input: mountainArr = [1,2,3,4,5,3,1], target = 3

Output: 2

3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2

Input: mountainArr = [0,1,2,4,2,1], target = 3

Output: -1

3 does not exist in the array, so we return -1.

Constraints

3 <= mountainArr.length() <= 104
0 <= target <= 109
0 <= mountainArr.get(index) <= 109

Solution Approach

Identify the Peak Using Binary Search

Use binary search to find the peak index where the sequence transitions from ascending to descending. Compare mid elements to neighbors to decide direction, ensuring O(log N) queries.

Search Ascending Side

Perform standard binary search on the ascending left portion up to the peak. Return the index if the target is found; otherwise, proceed to the descending side.

Search Descending Side

Perform reversed binary search on the descending right portion from peak to end. Because this side decreases, compare inversely to locate the target while minimizing get() calls.

Complexity Analysis

Metric	Value
Time	O(\log N)
Space	O(\log N)

Time complexity is O(log N) for each binary search step, first for peak identification, then for ascending and descending searches. Space complexity is O(log N) due to recursion stack or iterative binary search bookkeeping.

What Interviewers Usually Probe

Expect candidates to identify the mountain property and apply binary search.
Look for handling of interactive constraints and minimal array accesses.
Assess understanding of searching both ascending and descending segments separately.

Common Pitfalls or Variants

Common pitfalls

Failing to find the true peak before searching both sides.
Applying standard binary search without adjusting for descending portion.
Exceeding interactive call limits by redundant get() requests.

Follow-up variants

Find the maximum element in a mountain array without a target search.
Locate multiple targets in a mountain array and return all indices efficiently.
Determine if a value exists anywhere in the array with minimal get() calls.

FAQ

What is a mountain array in the context of this problem?

A mountain array strictly increases to a peak and then strictly decreases. Recognizing this structure is key to applying binary search correctly.

How do I efficiently find a target in a mountain array?

First locate the peak using binary search, then perform separate binary searches on the ascending and descending segments to find the minimum index.

Why does searching the descending side require a reversed comparison?

Because the descending side decreases, you must invert comparisons to maintain correct binary search behavior and avoid missing the target.

What are the interactive constraints in Find in Mountain Array?

You can only access the array via mountainArr.get(index) and length(), so minimizing calls is crucial to meet efficiency requirements.

Can GhostInterview show the pattern of binary search over the valid answer space?

Yes, it highlights how to apply binary search to both sides of the peak efficiently, emphasizing minimal queries and correct index selection.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
# class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:


class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        def search(l: int, r: int, k: int) -> int:
            while l < r:
                mid = (l + r) >> 1
                if k * mountain_arr.get(mid) >= k * target:
                    r = mid
                else:
                    l = mid + 1
            return -1 if mountain_arr.get(l) != target else l

        n = mountain_arr.length()
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) >> 1
            if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
                r = mid
            else:
                l = mid + 1
        ans = search(0, l, 1)
        return search(l + 1, n - 1, -1) if ans == -1 else ans

Continue Practicing

#1146 snapshot array #1157 online majority element in subarray #1027 longest arithmetic subsequence