Find in Mountain Array - Practice Coding Problems

Find in Mountain Array - 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.

Important: 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.

Input & Output

Example 1 — Basic Mountain Search

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

› Output: 2

💡 Note: The mountain array is [1,2,3,4,5,3,1] with peak at index 4 (value 5). Target 3 appears at indices 2 and 5, so return the minimum index 2.

Example 2 — Target Not Found

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

› Output: -1

💡 Note: The mountain array is [0,1,2,4,2,1] with peak at index 3 (value 4). Target 3 does not exist in the array, so return -1.

Example 3 — Target at Peak

$ Input: mountain_arr = [1,2,0,1,0], target = 0

› Output: 2

💡 Note: The mountain array is [1,2,0,1,0] with peak at index 1 (value 2). Target 0 appears at indices 2 and 4, so return the minimum index 2.

Constraints

3 ≤ mountain_arr.length() ≤ 10⁴
0 ≤ target ≤ 10⁹
mountain_arr is guaranteed to be a mountain array

Visualization

Tap to expand

Understanding the Visualization

Input

Mountain array [1,2,3,4,5,3,1] and target 3

Process

Find peak, then binary search left and right sides

Output

Return minimum index where target is found

Key Takeaway

🎯 Key Insight: A mountain array is just two sorted arrays joined at a peak - use binary search on each part separately

Asked in

G Google 45 f Facebook 38 a Amazon 32 A Apple 25

The key insight is that a mountain array has exactly one peak, dividing it into an ascending left side and descending right side. We can use three binary searches: first to find the peak, then search the left ascending side, and finally search the right descending side if needed. This approach uses only O(log n) API calls. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Search every position in the mountain array from left to right
Triple Binary Search	O(log n)	O(1)	Find peak with binary search, then search left and right sides separately

Linear Search — Algorithm Steps

Step 1: Iterate from index 0 to length-1
Step 2: Check if mountainArr.get(i) equals target
Step 3: Return first matching index or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at index 0

Check

Compare each element with target

Found

Return first matching index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* arr;
    int size;
    int callCount;
} MountainArray;

int get(MountainArray* mountain_arr, int index) {
    mountain_arr->callCount++;
    return mountain_arr->arr[index];
}

int length(MountainArray* mountain_arr) {
    return mountain_arr->size;
}

int solution(MountainArray* mountain_arr, int target) {
    int n = length(mountain_arr);
    for (int i = 0; i < n; i++) {
        if (get(mountain_arr, i) == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    MountainArray mountain_arr = {arr, size, 0};
    int result = solution(&mountain_arr, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through all n elements

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler