LeetCode 1095 - Find in Mountain Array

This problem gives us a special type of array called a mountain array. A mountain array strictly increases until it reaches a single peak element, then strictly decreases afterward. For example: increases up to 5, then decreases.

leetcodehardarraybinary-searchinteractive

LeetCode Problem 1095

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Interactive

Solution

Problem Understanding

This problem gives us a special type of array called a mountain array. A mountain array strictly increases until it reaches a single peak element, then strictly decreases afterward.

For example:

1 2 3 5 4 2

increases up to 5, then decreases.

The challenge is that this is an interactive problem. We cannot directly access the array. Instead, we can only use two API methods:

mountainArr.get(index)
mountainArr.length()

The goal is to find the smallest index where the value equals target. If the target appears multiple times, we must return the leftmost occurrence. If it does not exist, we return -1.

The mountain structure creates two sorted regions:

  1. An ascending portion from the beginning to the peak
  2. A descending portion from the peak to the end

This structure is extremely important because sorted regions allow binary search.

The constraints also matter:

  • The array length can be up to 10^4
  • We are limited to at most 100 calls to get()

A naive linear scan could require up to 10^4 API calls, which would immediately fail the interactive constraint. Therefore, we need an algorithm based primarily on binary search.

There are several important edge cases to keep in mind:

  • The target may appear on both sides of the peak
  • The target may not exist at all
  • The target may be the peak itself
  • The target may appear only in the descending half
  • Because we must return the minimum index, we must search the ascending half first
  • The peak is guaranteed to exist because the input is guaranteed to be a valid mountain array

Approaches

Brute Force Approach

The simplest solution is to iterate through every index from left to right and call:

mountainArr.get(i)

If the value equals the target, return the index immediately.

This works because eventually every position is checked, so if the target exists we will find the leftmost occurrence first.

However, this approach is far too expensive for the interactive constraints. In the worst case, we would make O(n) calls to get(), potentially up to 10^4 calls, while the problem only allows 100.

Therefore, we need a logarithmic solution.

Optimal Approach

The key insight is that a mountain array contains two sorted regions:

  • Increasing section
  • Decreasing section

Binary search works on sorted data, so we can use it multiple times.

The algorithm has three major phases:

  1. Find the peak index using binary search
  2. Binary search the ascending half
  3. If not found, binary search the descending half

Finding the peak works because:

  • If arr[mid] < arr[mid + 1], we are on the increasing slope, so the peak is to the right
  • Otherwise, we are on the decreasing slope or at the peak, so the peak is at mid or to the left

Once the peak is found:

  • The left side is strictly increasing, so we use normal binary search
  • The right side is strictly decreasing, so we use modified binary search with reversed comparisons

Because each phase uses binary search, the total complexity remains logarithmic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Sequentially scans every element
Optimal O(log n) O(1) Uses binary search on peak and both sorted halves

Algorithm Walkthrough

  1. First, determine the length of the mountain array using mountainArr.length().
  2. Use binary search to locate the peak element. At each midpoint:
  • Compare mountainArr.get(mid) and mountainArr.get(mid + 1)
  • If the right value is larger, we are still climbing upward, so move left boundary to mid + 1
  • Otherwise, we are descending or already at the peak, so move right boundary to mid
  1. Continue until the left and right pointers meet. That position is the peak index.
  2. Perform a standard binary search on the ascending portion from index 0 to peak.
  • If the midpoint value is smaller than target, move right
  • If larger, move left
  • If equal, return immediately

We search this side first because the problem asks for the minimum index. 5. If the target was not found on the left side, perform another binary search on the descending portion from peak + 1 to n - 1.

Since this half is sorted in descending order:

  • If midpoint value is greater than target, move right
  • If midpoint value is smaller than target, move left
  1. If neither search finds the target, return -1.

Why it works

The correctness comes from the mountain array properties.

The peak search always converges correctly because each comparison tells us which side of the peak we are on. The increasing and decreasing regions are strictly monotonic, so binary search is valid on both halves.

Searching the ascending half first guarantees that if the target exists in both halves, we return the smaller index.

Python Solution

# """
# 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:

from typing import Protocol

class Solution:
    def findInMountainArray(
        self,
        target: int,
        mountainArr: 'MountainArray'
    ) -> int:

        n = mountainArr.length()

        # Find peak index
        left = 0
        right = n - 1

        while left < right:
            mid = (left + right) // 2

            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                left = mid + 1
            else:
                right = mid

        peak = left

        # Binary search on increasing side
        left = 0
        right = peak

        while left <= right:
            mid = (left + right) // 2
            value = mountainArr.get(mid)

            if value == target:
                return mid

            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        # Binary search on decreasing side
        left = peak + 1
        right = n - 1

        while left <= right:
            mid = (left + right) // 2
            value = mountainArr.get(mid)

            if value == target:
                return mid

            if value > target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

The implementation begins by locating the peak element using binary search. Instead of checking whether a position is the peak directly, the algorithm compares adjacent elements to determine whether the search is currently on the increasing or decreasing slope.

Once the peak is identified, the code performs a standard binary search on the left half because that region is strictly increasing.

If the target is not found there, the algorithm searches the right half. Since the right side is strictly decreasing, the comparison directions are reversed.

The implementation uses only constant extra space and keeps the number of get() calls logarithmic.

Go Solution

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * type MountainArray struct {
 * }
 *
 * func (this *MountainArray) get(index int) int {}
 * func (this *MountainArray) length() int {}
 */

func findInMountainArray(target int, mountainArr *MountainArray) int {
	n := mountainArr.length()

	// Find peak index
	left, right := 0, n-1

	for left < right {
		mid := left + (right-left)/2

		if mountainArr.get(mid) < mountainArr.get(mid+1) {
			left = mid + 1
		} else {
			right = mid
		}
	}

	peak := left

	// Binary search on increasing side
	left, right = 0, peak

	for left <= right {
		mid := left + (right-left)/2
		value := mountainArr.get(mid)

		if value == target {
			return mid
		}

		if value < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	// Binary search on decreasing side
	left, right = peak+1, n-1

	for left <= right {
		mid := left + (right-left)/2
		value := mountainArr.get(mid)

		if value == target {
			return mid
		}

		if value > target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return -1
}

The Go implementation follows the same algorithmic structure as the Python version.

One important Go-specific detail is the midpoint calculation:

mid := left + (right-left)/2

This form avoids potential integer overflow, which is a common binary search best practice in Go and other statically typed languages.

Go also uses explicit variable declarations and pointer receivers for the interactive MountainArray interface.

Worked Examples

Example 1

mountainArr = [1,2,3,4,5,3,1]
target = 3

Step 1, Find Peak

left right mid arr[mid] arr[mid+1] Action
0 6 3 4 5 move right
4 6 5 3 1 move left
4 5 4 5 3 move left

Peak index becomes:

peak = 4
value = 5

Step 2, Search Increasing Half

Search range:

[1,2,3,4,5]
left right mid value Action
0 4 2 3 found

Return:

2

Example 2

mountainArr = [0,1,2,4,2,1]
target = 3

Step 1, Find Peak

left right mid arr[mid] arr[mid+1] Action
0 5 2 2 4 move right
3 5 4 2 1 move left
3 4 3 4 2 move left

Peak index:

peak = 3

Step 2, Search Increasing Half

[0,1,2,4]

Target not found.

Step 3, Search Decreasing Half

[2,1]

Target still not found.

Return:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Three binary searches, each logarithmic
Space O(1) Only a few variables are used

The peak search takes O(log n) time because the search range is halved each iteration. Each subsequent binary search also takes O(log n) time. Since logarithmic factors add rather than multiply, the total remains O(log n).

The algorithm uses constant extra memory because no auxiliary data structures are allocated.

Test Cases

class MockMountainArray:
    def __init__(self, arr):
        self.arr = arr

    def get(self, index):
        return self.arr[index]

    def length(self):
        return len(self.arr)

solution = Solution()

# Example 1
assert solution.findInMountainArray(
    3,
    MockMountainArray([1,2,3,4,5,3,1])
) == 2  # target appears twice, return leftmost

# Example 2
assert solution.findInMountainArray(
    3,
    MockMountainArray([0,1,2,4,2,1])
) == -1  # target absent

# Target is peak
assert solution.findInMountainArray(
    5,
    MockMountainArray([1,2,3,5,4,2])
) == 3  # peak element

# Target only on descending side
assert solution.findInMountainArray(
    4,
    MockMountainArray([1,3,5,7,6,4,2])
) == 5  # descending search

# Smallest valid mountain array
assert solution.findInMountainArray(
    2,
    MockMountainArray([1,2,1])
) == 1  # minimal size

# Target at beginning
assert solution.findInMountainArray(
    1,
    MockMountainArray([1,5,3])
) == 0  # first element

# Target at end
assert solution.findInMountainArray(
    1,
    MockMountainArray([0,2,4,3,1])
) == 4  # last element

# Target appears on both sides
assert solution.findInMountainArray(
    2,
    MockMountainArray([1,2,4,5,3,2,1])
) == 1  # must return smallest index

# Large increasing then decreasing
assert solution.findInMountainArray(
    8,
    MockMountainArray([1,3,5,7,9,8,6,4,2])
) == 5  # descending half

# Target smaller than all values
assert solution.findInMountainArray(
    0,
    MockMountainArray([1,3,5,4,2])
) == -1  # below minimum
Test Why
[1,2,3,4,5,3,1], target=3 Validates duplicate appearance across both halves
[0,1,2,4,2,1], target=3 Validates missing target
[1,2,3,5,4,2], target=5 Validates peak handling
[1,3,5,7,6,4,2], target=4 Validates descending binary search
[1,2,1], target=2 Validates smallest valid mountain array
[1,5,3], target=1 Validates first index
[0,2,4,3,1], target=1 Validates last index
[1,2,4,5,3,2,1], target=2 Ensures smallest index is returned
[1,3,5,7,9,8,6,4,2], target=8 Validates larger descending region
[1,3,5,4,2], target=0 Validates impossible low target

Edge Cases

One important edge case occurs when the target appears in both halves of the mountain array. For example:

[1,2,3,5,3,1]

with target 3.

A careless implementation might search the descending half first and incorrectly return index 4 instead of index 2. This implementation avoids that issue by always searching the increasing half before the decreasing half.

Another important edge case is when the target equals the peak element itself. Since the peak belongs to the ascending search range, the first binary search correctly detects and returns it immediately. This prevents missing the peak or searching unnecessary ranges afterward.

A third edge case involves very small valid mountain arrays such as:

[1,2,1]

The peak search still works correctly because the binary search logic only relies on adjacent comparisons. The algorithm safely converges even when the array contains only three elements.

Another subtle case is when the target exists only in the descending half. Standard binary search assumes ascending order, so reusing the same comparison logic would fail. This implementation explicitly reverses the comparison direction for the descending section, ensuring correctness.