Logo

Kode$word

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

11 views
0
0
LeetCodeBinary SearchMountain ArrayMediumJava
Github icon

Try the Question

Before reading the explanation, try solving the problem yourself:

👉 https://leetcode.com/problems/peak-index-in-a-mountain-array/

Solving it first helps strengthen your problem-solving intuition, especially for binary search problems.


Problem Statement

You are given an integer array arr that is guaranteed to be a mountain array.

A mountain array is defined as an array where:

  1. Elements strictly increase until a peak element.
  2. After the peak, elements strictly decrease.

Example:

[0, 2, 5, 7, 6, 3, 1]
^
peak

Your task is to return the index of the peak element.

Constraints

3 <= arr.length <= 10^5
0 <= arr[i] <= 10^6
arr is guaranteed to be a mountain array

Important implications:

  1. The peak always exists.
  2. There will be exactly one peak.
  3. The array strictly increases before the peak and strictly decreases after it.


Example Walkthrough

Example 1

Input

arr = [0,1,0]

Visualization

0 1 0
^

Output

1

Example 2

Input

arr = [0,2,1,0]

Visualization

0 2 1 0
^

Output

1

Example 3

Input

arr = [0,10,5,2]

Visualization

0 10 5 2
^

Output

1


Understanding the Mountain Array Structure

A mountain array always looks like this:

increasing → peak → decreasing

Graphically:

peak
/\
/ \
/ \

Because of this structure:

  1. Before the peak → numbers increase
  2. After the peak → numbers decrease

This property makes the problem perfect for binary search.


Approach 1 — Brute Force (Check Every Element)

The simplest way is to check every element and determine if it is greater than its neighbors.

Algorithm

  1. Traverse the array from index 1 to n-2.
  2. For each element check:
arr[i] > arr[i-1] AND arr[i] > arr[i+1]
  1. If true, return i.

Implementation

public int peakIndexInMountainArray(int[] arr) {

for(int i = 1; i < arr.length - 1; i++){

if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){
return i;
}

}

return -1;
}

Time Complexity

O(n)

We may need to check every element.

Space Complexity

O(1)


Approach 2 — Linear Scan Using Increasing Trend

Since the array first increases then decreases, we can detect where the increase stops.

Key Idea

Traverse the array and check when:

arr[i] > arr[i+1]

This means we reached the peak.

Implementation

public int peakIndexInMountainArray(int[] arr) {

for(int i = 0; i < arr.length - 1; i++){

if(arr[i] > arr[i+1]){
return i;
}

}

return -1;
}

Example

0 2 5 7 6 3 1
^

At index 3:

7 > 6

So index 3 is the peak.

Time Complexity

O(n)

Space Complexity

O(1)


Approach 3 — Modified Binary Search (Optimal Solution)

Because the array has a mountain structure, binary search can be used.

Core Intuition

Compare:

arr[mid]
arr[mid+1]

Two situations are possible.

Case 1 — Increasing Slope

arr[mid] < arr[mid+1]

Example:

1 3 5 7
^

This means the peak is on the right side.

Move the search space to the right.

left = mid + 1

Case 2 — Decreasing Slope

arr[mid] > arr[mid+1]

Example:

7 5 3 1
^

This means the peak lies on the left side including mid.

right = mid


Optimal Java Implementation

class Solution {

public int peakIndexInMountainArray(int[] arr) {

int i = 0;
int j = arr.length - 1;

while(i < j){

int mid = i + (j - i) / 2;

if(arr[mid] < arr[mid + 1]){
i = mid + 1;
}
else{
j = mid;
}
}

return i;
}
}


Step-by-Step Example

Array

[0,2,5,7,6,3,1]

Iteration 1

mid = 3
arr[mid] = 7
arr[mid+1] = 6

Decreasing slope → move left.

Iteration 2

Search space narrows until:

peak index = 3

Time Complexity

O(log n)

Binary search halves the search space each iteration.

Space Complexity

O(1)

No extra memory is required.


Why Binary Search Works Here

Because the array behaves like a mountain curve.

If you are standing at index mid:

  1. If the right side is higher, go right.
  2. If the left side is higher, go left.

Eventually you will reach the top of the mountain (the peak).


Key Takeaways

✔ A mountain array increases then decreases

✔ There is exactly one peak

✔ Brute force and linear scan work in O(n) time

✔ Binary search exploits the mountain structure

✔ Optimal solution runs in O(log n) time


Final Thoughts

This problem is a classic example of binary search applied to array patterns rather than sorted values.

Understanding the slope comparison technique used here will help solve other problems such as:

  1. Find Peak Element
  2. Mountain Array Search
  3. Bitonic Array Problems

Mastering these patterns significantly improves binary search problem-solving skills for coding interviews.

Related Articles

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Learn how to efficiently search for an element in a rotated sorted array using binary search. This guide explains the intuition, multiple strategies, and a clean Java implementation that achieves O(log n) time complexity.

Read Article
Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article

Ai Assistant Kas