Skip to main content
Talentd

Find in Mountain Array - Solution & Explanation

HardArrayBinary SearchInteractive21 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

(This problem is an interactive problem.)

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some i with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

  • MountainArray.get(k) returns the element of the array at index k (0-indexed).
  • MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

Example 1:

Input: mountainArr = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 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
Explanation: 3 does not exist in the array, so we return -1.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a mountain array where values strictly increase to a peak and then strictly decrease. The task is to find the index of a target value using only the provided MountainArray.get() API while minimizing calls to the array.

Approach 1: Brute-force Linear Scan (O(n) time, O(1) space)

The simplest strategy is to iterate through the array from index 0 to n - 1 and call get(i) for each position. If the returned value matches the target, return the index immediately. This approach works because every element is checked exactly once. However, the problem is interactive and restricts the number of API calls, so scanning the entire array can exceed the allowed limit for large inputs. Time complexity is O(n) and extra space is O(1). This approach mainly helps verify correctness before optimizing.

Approach 2: Binary Search with Peak Finding (O(log n) time, O(1) space)

A mountain array has two sorted regions: strictly increasing before the peak and strictly decreasing after it. First locate the peak index using binary search. Compare get(mid) with get(mid + 1). If the sequence is rising, move right; otherwise move left. This identifies the maximum element in O(log n) calls.

Once the peak is known, run two separate binary searches. Search the left side [0, peak] as a normal ascending array. If the target is not found, search the right side [peak + 1, n - 1] but reverse the comparison logic because that portion is descending. Each search takes O(log n), keeping the total time complexity O(log n) and space O(1).

This approach leverages the structural guarantee of a mountain array instead of scanning blindly. It also minimizes calls to the MountainArray interface, which is critical for interactive problems. The algorithm mainly relies on concepts from arrays and interactive problems where API usage is constrained.

Recommended for interviews: Binary search with peak finding is the expected solution. Interviewers want to see that you recognize the two monotonic segments and apply binary search correctly on both sides. Showing the brute-force scan first demonstrates baseline reasoning, but the optimized O(log n) approach proves you understand how to exploit problem structure.

Approach 1: Binary Search with Peak Finding

In this approach, the task is broken into three main steps:

  • First, find the peak element of the mountain array using binary search. The peak is defined as the highest element where arr[i] > arr[i+1] and arr[i] > arr[i-1].
  • Once the peak is identified, the array is split into two parts: one is increasing and the other is decreasing. Perform binary search separately on these two parts.
  • On the increasing part of the array (from the start to the peak), perform binary search for the target. If found, note the index.
  • On the decreasing part of the array (from peak to the end), perform a descending order binary search for the target. If found, compare the index with the previously found index in the increasing part to ensure the minimum index is returned.

This C implementation is efficient as it implements a binary search method to find the peak in O(log n) time. After finding the peak, it searches both halves of the mountain array for the target using two separate binary searches. One binary search is for the increasing part (left of the peak) with an increasing order binary search, and another one in the decreasing half (right of the peak) with a decreasing order binary search. As it is a binary search, each takes O(log n) time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) for peak finding and 2 * O(log n) for the two binary searches.
Total: O(log n).
Space Complexity: O(1) because we use a constant amount of space.

Try this approach in the editor →

Approach 2: Brute-force Approach

This approach involves directly accessing each element linearly until the condition is satisfied (even though this is not allowed by the problem constraints). It is less optimal and efficient compared to the above implementations, requiring traversal of the entire array.

The brute-force approach directly scans through the mountain array from the start to the finish, checking each element against the target. If an element equals the target, it returns the index. Otherwise, it returns -1. This basic method is straightforward but inefficient due to its time complexity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) as each element could potentially be checked once.
Space Complexity: O(1) as no extra space is used except for variables.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search with Peak Finding

Time Complexity: O(log n) for peak finding and 2 * O(log n) for the two binary searches.
Total: O(log n).
Space Complexity: O(1) because we use a constant amount of space.

Brute-force Approach

Time Complexity: O(n) as each element could potentially be checked once.
Space Complexity: O(1) as no extra space is used except for variables.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-force Linear ScanO(n)O(1)Quick baseline solution or when constraints are very small
Binary Search with Peak FindingO(log n)O(1)Optimal solution for mountain arrays and interactive API limits

Video Solution

Find in Mountain Array - Leetcode 1095 - Python • NeetCodeIO • 19,406 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find in Mountain Array easy or hard?
Find in Mountain Array is classified as a Hard problem on LeetCode. The difficulty comes from combining peak detection, two directional binary searches, and restrictions on the number of API calls.
Find in Mountain Array Python/Java solution
Implement the optimized method by first locating the peak with binary search and then searching both sides. The same algorithm works across Python, Java, C++, C, C#, and JavaScript because it only requires index-based comparisons using the MountainArray API.
How to solve Find in Mountain Array in O(log n)?
First locate the peak using binary search by comparing mid and mid+1 values. After finding the peak index, run a standard binary search on the left increasing section. If the target is not found, run another binary search on the right decreasing section with reversed comparisons.
What is the best approach for Find in Mountain Array?
The best approach uses binary search to first locate the peak of the mountain array and then perform two binary searches on the increasing and decreasing halves. This leverages the array's structure and minimizes API calls. The total time complexity is O(log n) with O(1) space.
Is Find in Mountain Array asked at Google/Amazon/Meta?
Find in Mountain Array appears in interview preparation sets commonly associated with companies like Google and Amazon because it combines binary search with constrained API access. The problem tests understanding of monotonic segments and efficient search strategies.
What data structure is used in Find in Mountain Array?
The core data structure is an array accessed through the MountainArray interface. The algorithm relies on binary search operations over the array indices rather than additional structures, keeping space complexity constant.
What is the time complexity of Find in Mountain Array?
The optimal solution runs in O(log n) time. One binary search identifies the peak element and two additional binary searches check the ascending and descending segments. Each step takes logarithmic time, and space complexity remains O(1).

Ready to solve this problem?

Practice Find in Mountain Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Good Days to Rob the Bank

Next

Find Indices of Stable Mountains