Find in Mountain Array

Find in Mountain Array

What is this problem about?

The Find in Mountain Array interview question is an optimization puzzle. A "mountain array" increases to a peak and then decreases. You are given a hidden mountain array (accessible only via an get(index) method) and a target value. You need to find the minimum index such that MountainArray.get(index) == target. You must minimize the number of calls to the get method.

Why is this asked in interviews?

This Find in Mountain Array coding problem is a frequent "Hard" challenge at Amazon and Google. It tests your ability to combine multiple Binary Search interview patterns. You can't just search linearly; you must use binary search to find the peak, then binary search the increasing side, and finally binary search the decreasing side. It evaluates your precision with search ranges and method-call budgets.

Algorithmic pattern used

The problem is solved in three distinct Binary Search phases:

1. Find the Peak: Binary search to find index $i$ where $arr[i] > arr[i-1]$ and $arr[i] > arr[i+1]$.
2. Search Increasing Side: Perform a standard binary search on [0, peak] for the target.
3. Search Decreasing Side: If not found, perform a descending binary search on [peak + 1, length - 1].

Example explanation

Mountain: [1, 2, 3, 4, 5, 3, 1], Target: 3.

1. Find Peak: Binary search identifies index 4 (value 5) as the peak.
2. Search Left [0, 4]: [1, 2, 3, 4, 5]. Target 3 found at index 2. Result: 2. (Even though 3 exists at index 5, 2 is smaller).

Common mistakes candidates make

• Method Call Limit: Calling get(index) too many times. You should store the result of get(mid) to avoid redundant calls.
• Descending Search: Using standard binary search logic on the decreasing side, which will fail because the values are in reverse order.
• Peak logic: Getting the peak-finding condition slightly wrong (e.g., handling the boundaries of the array).

Interview preparation tip

This is a "Triple Binary Search" problem. Ensure you can write a generalized binarySearch function that takes a flag for isAscending. This keeps your code modular and reduces errors during the high-pressure search phases.