LogoKode$word

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.

Krishna Shrivastava
31 views
LinkedInGithubX
0
0
LeetCodeBinary SearchMountain ArrayMediumJava
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)
Listen to articleAudio version
Ad

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

LeetCode 845: Longest Mountain in Array – Java Solution with Peak Expansion

LeetCode 845: Longest Mountain in Array – Java Solution with Peak Expansion

Learn how to identify mountain peaks, expand in both directions, and find the longest valid mountain subarray using O(n) time and O(1) extra space.

Read Article
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
LeetCode 55: Jump Game – Java Greedy Solution with Explanation and Dry Run

LeetCode 55: Jump Game – Java Greedy Solution with Explanation and Dry Run

Learn how to solve LeetCode 55 Jump Game using a simple greedy approach by tracking the farthest index reachable at every step.

Read Article
LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

Learn how to solve LeetCode 3751 Total Waviness of Numbers in Range I using a clean Java brute force approach. Includes intuition, peak and valley logic, dry run, complexity analysis, and interview explanation.

Read Article
Ai Assistant Kas
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852) | Kodesword | Kode$word