This problem is solved by first identifying the peak of the mountain array using binary search, then searching both ascending and descending sides separately. You must interact with the array through get() calls, ensuring minimal queries. Binary search over the correct segment guarantees the minimum index or -1 if the target is absent, aligning with the interactive constraints.
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.
How GhostInterview Helps
- GhostInterview provides step-by-step guidance for identifying the peak and managing interactive queries.
- It highlights the exact binary search segments needed to locate the target efficiently.
- The solver ensures minimal array accesses and correct index retrieval across ascending and descending sections.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Find in Mountain Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find in Mountain Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Implement a SnapshotArray that efficiently tracks element changes and retrieves past states using array scanning and hash lookup patterns.
Open problem page#1157 Online Majority Element In SubarrayEfficiently find the majority element in any subarray using a data structure optimized for multiple range queries.
Open problem page#1027 Longest Arithmetic SubsequenceFind the length of the longest arithmetic subsequence in a given integer array using scanning and hash-based lookup.
Open problem page