Log inSign up
mediumLeetCodeNot Started

Peak Index in a Mountain Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

An array arr is a mountain if the following properties hold: - 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 arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1 · Standard Mountain Peak:

Input: arr = [0, 1, 0]
Output: 1
Explanation: Peak is at index 1 with value 1.

Example 2 · Ascending and Descending Slopes:

Input: arr = [0, 2, 1, 0]
Output: 1
Explanation: arr[1] = 2 is strictly greater than both neighbors.

Example 3 · Larger Mountain Array:

Input: arr = [0, 10, 5, 2]
Output: 1
Explanation: arr[1] = 10 is the maximum element.

Constraints:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • arr is guaranteed to be a mountain array.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Binary search boundary conditions
  • Monotonic properties & slope comparison

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify binary search applicability on unimodal functions.
  • Formulate robust mid-point slope comparisons avoiding index out of bounds.
  • Master the low < high convergence pattern for peak finding.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Find Peak Element (LeetCode 162)Search in Rotated Sorted Array

1. Linear Scan for Peak (Brute Force)

Intuition

By the mountain array definition, the array strictly increases up to the peak index i, and strictly decreases afterwards. A linear scan finds the first index i where arr[i] > arr[i + 1]. This index i is guaranteed to be the peak.

When to apply: Use to verify the mountain array property definition before optimizing to binary search.

Brute force — inspect every value

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
A peak is greater than its immediate neighbors
Visual state
Values and pointers at this exact step
array
S
0
2
5
3
1
0
1
2
3
4
Variables at this step
i
0
Check / comparison
Start at index 0.
Decision / next transition
Check each element for a peak.
Why this step matters

A peak is greater than its immediate neighbors.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int peakIndexInMountainArray(int[] arr) {
4 int i = 0;
5 while (arr[i] < arr[i + 1]) {
6 i++;
7 }
8 return i;
9 }
10 }
11
12 public static void main(String[] args) {
13 Solution sol = new Solution();
14 int[] arr = {0, 2, 5, 10, 4, 1};
15 System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
16 }
17}

Time & Space Complexity

  • Time complexity: O(n) — In the worst case, the peak is near the end, scanning up to n elements.
  • Space complexity: O(1) — No additional memory allocated.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Two-Pointer Converging Scan (Better)

Intuition

Initialize low = 0 and high = n - 1. While low < high: if arr[low] < arr[low + 1], low++; if arr[high] < arr[high - 1], high--. Both pointers march upwards toward the mountain summit, converging on the peak.

When to apply: Use to understand the bidirectional narrowing of unimodal search spaces.

Better — scan adjacent slopes

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
A rising slope means the peak has not yet been passed
Visual state
Values and pointers at this exact step
array
S
0
2
5
3
1
0
1
2
3
4
Variables at this step
i
0
Check / comparison
Compare arr[0] and arr[1]: 0 < 2.
Decision / next transition
Move right while the slope rises.
Why this step matters

A rising slope means the peak has not yet been passed.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int peakIndexInMountainArray(int[] arr) {
4 int low = 0, high = arr.length - 1;
5 while (low < high) {
6 if (arr[low] < arr[low + 1]) low++;
7 if (arr[high] < arr[high - 1]) high--;
8 }
9 return low;
10 }
11 }
12
13 public static void main(String[] args) {
14 Solution sol = new Solution();
15 int[] arr = {0, 2, 5, 10, 4, 1};
16 System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
17 }
18}

Time & Space Complexity

  • Time complexity: O(n) — Pointers advance inward, completing at most n steps.
  • Space complexity: O(1) — O(1) auxiliary pointer variables.

3. Binary Search on Mountain Slope (Optimal)

Intuition

1. If arr[mid] < arr[mid + 1], we are on the strictly ascending left flank; the peak must be to the right, so low = mid + 1. 2. If arr[mid] > arr[mid + 1], we are either at the peak or on the strictly descending right flank; the peak is at or to the left of mid, so high = mid. 3. When low == high, both pointers converge exactly at the unique summit.

When to apply: Use as the optimal O(log n) solution for finding the peak in any unimodal mountain array.

Optimal — binary search on the slope

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
A falling slope means the peak is at mid or to its left
Visual state
Values and pointers at this exact step
array
S
0
2
5
3
1
0
1
2
3
4
Variables at this step
l
0
r
2
mid
2
Check / comparison
l=0, r=4, mid=2; arr[mid]=5 > arr[mid+1]=3.
Decision / next transition
Set r=mid=2.
Why this step matters

A falling slope means the peak is at mid or to its left.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int peakIndexInMountainArray(int[] arr) {
4 int low = 0, high = arr.length - 1;
5 while (low < high) {
6 int mid = low + (high - low) / 2;
7 if (arr[mid] < arr[mid + 1]) {
8 low = mid + 1;
9 } else {
10 high = mid;
11 }
12 }
13 return low;
14 }
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] arr = {0, 2, 5, 10, 4, 1};
20 System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
21 }
22}

Time & Space Complexity

  • Time complexity: O(log n) — The search space is cut in half at each step, taking at most ceil(log2(n)) iterations.
  • Space complexity: O(1) — O(1) memory using three scalar index variables (low, high, mid).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear ScanO(N)O(1)Iterate from left to right and return the first index i where arr[i] > arr[i+1].Inspects up to N elements sequentially.
2.Better — Ternary SearchO(log_3 N)O(1)Split range into 3 parts using two midpoints m1 and m2 to narrow down the unimodal peak.2 comparisons per step vs 1 comparison in binary search.
3.Optimal — Binary Search on SlopeOptimalO(log N)O(1)Standard binary search comparing arr[mid] with arr[mid+1] to bisect the search space.None; optimal for search.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Peak Index in a Mountain Array?

2.Why is the brute force approach suboptimal for large inputs in Peak Index in a Mountain Array?

3.Which data structure or technique enables the optimal solution for Peak Index in a Mountain Array?

Back to DSA Sheet