Naive Pseudo-code:

text
function findInMountainArray(target, mountainArr):
    length = mountainArr.length()
    for i from 0 to length - 1:
        val = mountainArr.get(i)
        if val == target:
            return i
    return -1

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the length of the mountain array.
• Space Complexity: $O(1)$.

Why it fails: The problem strictly enforces an interaction limit. With $N$ up to $10,000$, a linear scan requires up to 10,000 calls to MountainArray.get(). The limit is 100 calls. Since $100 \ll 10,000$, this approach will immediately trigger a "Wrong Answer" or disqualification due to excessive API usage. We must minimize calls using an $O(\log N)$ strategy.

Core Insight for Find in Mountain Array

The core difficulty in LeetCode 1095 is that the entire array is not sorted in a single direction. Standard binary search requires monotonic data (always increasing or always decreasing). A mountain array is bitonic: it increases, reaches a peak, and then decreases.

However, the peak element acts as a boundary.

1. To the left of the peak (inclusive of the peak), the array is strictly ascending.
2. To the right of the peak, the array is strictly descending.

If we can identify the index of the peak, we can treat the problem as two independent binary search problems on sorted arrays.

To find the peak efficiently, we utilize the derivative (slope) logic used in finding extrema. By comparing mid and mid + 1, we can determine if we are on the ascending slope or the descending slope:

• If arr[mid] < arr[mid + 1], we are climbing up; the peak is to the right.
• If arr[mid] > arr[mid + 1], we are climbing down (or at the peak); the actual peak is at mid or to the left.

Visual Description: Imagine plotting the array values on a graph where the Y-axis is the value and X-axis is the index. The shape forms an inverted "V".

1. Phase 1 (Peak Finding): We probe the middle of the range. If the slope at that point is positive, we discard the left half. If the slope is negative, we discard the right half. This narrows the search space to the single highest point (the peak).
2. Phase 2 (Target Search): Once the peak index is fixed, the graph is split into a "Left Wing" (strictly increasing) and a "Right Wing" (strictly decreasing). We perform binary search on the Left Wing first. If the target is found, we return that index (since we need the minimum index). If not, we perform binary search on the Right Wing.

Execution Flow

Let's trace the algorithm with mountainArr = [1, 2, 3, 4, 5, 3, 1] and target = 3.

Step 1: Find Peak Index

• Range [0, 6]. mid = 3.
• Compare arr[3] (4) and arr[4] (5).
• Since $4 < 5$, we are ascending. Peak is to the right. New range [4, 6].
• mid = 5. Compare arr[5] (3) and arr[6] (1).
• Since $3 > 1$, we are descending. Peak is at or left of 5. New range [4, 5].
• mid = 4. Compare arr[4] (5) and arr[5] (3).
• Since $5 > 3$, we are descending. Peak is at or left of 4. New range [4, 4].
• low == high. Peak Index is 4 (Value is 5).

Step 2: Search Left (Ascending) [0, 4]

• Range [0, 4]. Target is 3.
• mid = 2. arr[2] is 3.
• Match found!
• Since we want the minimum index and we search the left side first, we return 2.

Note: If the target were 3 in the right half only (e.g., if the array were [1, 5, 3]), Step 2 would fail, and we would proceed to Step 3.

Proof of Correctness

The correctness relies on the Bitonic Property of the Mountain Array.

1. Peak Uniqueness: A mountain array has exactly one peak. The condition arr[i] < arr[i+1] is true for all $i < \text{peak}$ and false for all $i \geq \text{peak}$. This monotonicity in the slope allows binary search to converge on the peak index correctly.
2. Coverage: By splitting the array at the peak, we cover the entire search space. The left side [0, peak] is strictly increasing, and the right side [peak+1, end] is strictly decreasing.
3. Min Index Requirement: Searching the left subarray first ensures that if the target appears twice (once on each slope), we return the smaller index.

Reference Implementation

C++ Solution for LeetCode 1095

cpp
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        
        // 1. Find the peak index
        int low = 0;
        int high = n - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                // Ascending part, peak is to the right
                low = mid + 1;
            } else {
                // Descending part or peak, peak is left or here
                high = mid;
            }
        }
        int peakIndex = low;
        
        // 2. Search in the ascending part (left of peak)
        low = 0;
        high = peakIndex;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            if (val < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        // 3. Search in the descending part (right of peak)
        low = peakIndex + 1;
        high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            if (val < target) {
                // In descending order, smaller value means we are too far right
                high = mid - 1;
            } else {
                // Larger value means we are too far left
                low = mid + 1;
            }
        }
        
        return -1;
    }
};

Java Solution for LeetCode 1095

java
/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index);
 *     public int length();
 * }
 */
 
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();
        
        // 1. Find the peak index
        int low = 0;
        int high = length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                // We are in the increasing section
                low = mid + 1;
            } else {
                // We are in the decreasing section or at the peak
                high = mid;
            }
        }
        int peakIndex = low;
        
        // 2. Binary Search on the increasing subarray [0, peakIndex]
        int result = binarySearch(mountainArr, target, 0, peakIndex, true);
        if (result != -1) {
            return result;
        }
        
        // 3. Binary Search on the decreasing subarray [peakIndex + 1, length - 1]
        return binarySearch(mountainArr, target, peakIndex + 1, length - 1, false);
    }
    
    private int binarySearch(MountainArray arr, int target, int low, int high, boolean ascending) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int val = arr.get(mid);
            
            if (val == target) {
                return mid;
            }
            
            if (ascending) {
                if (val < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else {
                // Descending logic
                if (val < target) {
                    high = mid - 1; // Target is larger, move left
                } else {
                    low = mid + 1;  // Target is smaller, move right
                }
            }
        }
        return -1;
    }
}

Python Solution for LeetCode 1095

python
# """
# 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:
        n = mountain_arr.length()
        
        # 1. Find the peak index
        low, high = 0, n - 1
        while low < high:
            mid = (low + high) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                low = mid + 1
            else:
                high = mid
        peak_index = low
        
        # 2. Search in the ascending part
        low, high = 0, peak_index
        while low <= high:
            mid = (low + high) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                low = mid + 1
            else:
                high = mid - 1
                
        # 3. Search in the descending part
        low, high = peak_index + 1, n - 1
        while low <= high:
            mid = (low + high) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                # In descending, smaller value means go left (to larger values)
                high = mid - 1
            else:
                low = mid + 1
                
        return -1

Mistake 2: Caching the peak value but not the index.

• What: Finding the peak value correctly but failing to store its index to use as a boundary for subsequent searches.
• Why: The algorithm requires the index to split the array into [0, peakIndex] and [peakIndex + 1, end].
• Consequence: You cannot define the boundaries for the subsequent binary searches.

Mistake 3: Infinite loops during peak finding.

• What: Using high = mid - 1 or low = mid incorrectly without adjusting the loop condition or mid calculation.
• Why: Boundary conditions in binary search are subtle. If low and high are adjacent, mid might calculate to low, and if the logic doesn't advance pointers, the loop never terminates.
• Consequence: Time Limit Exceeded (TLE).