Find Peak Element

🎯

Find Peak Element

mediumBINARY_SEARCHGoogleAmazonFacebook

Imagine you are hiking on a mountain trail and want to find a peak point where the elevation is higher than its neighbors without checking every step.

💡 This problem is about finding a 'peak' element in an array where neighbors are smaller. Beginners often struggle because the problem looks like it needs a full scan, but it can be solved efficiently using a modified binary search by exploiting the 'go uphill' property.

📋

Problem Statement

Given an integer array nums, find a peak element, and return its index. An element is a peak if it is strictly greater than its neighbors. If the array contains multiple peaks, return the index to any of the peaks. You may imagine nums[-1] = nums[n] = -∞ (negative infinity).

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1nums[i] ≠ nums[i+1] for all valid i

💡

Example

Input"[1, 2, 3, 1]"

Output2

nums[2] = 3 is a peak because it is greater than neighbors 2 and 1.

Input"[1, 2, 1, 3, 5, 6, 4]"

Output1 or 5

nums[1] = 2 and nums[5] = 6 are both peaks.

• Single element array → index 0
• Strictly increasing array → last index is peak
• Strictly decreasing array → first index is peak
• Array with multiple peaks → any peak index is valid

⚠️

Common Mistakes

Not handling boundaries correctly

Index out of range errors or incorrect peak detection at edges

✅ Use virtual -∞ for out-of-bound neighbors or carefully check boundaries

Using mid instead of mid+1 in comparison

Incorrect direction choice leading to infinite loop or wrong answer

✅ Always compare nums[mid] with nums[mid+1] to decide direction

Returning mid instead of low or high after loop

May return incorrect index if loop ends with low != mid

✅ Return low (or high) after loop ends as they converge to peak

Assuming multiple peaks must be returned

Overcomplicates solution and wastes time

✅ Return any one peak as problem states multiple peaks are allowed

🧠

Brute Force (Linear Scan)

💡 This approach exists to build intuition by checking every element to see if it is a peak. It is simple but inefficient for large inputs.

Intuition

Check each element and compare it with neighbors to find a peak. Since neighbors are smaller, a peak is where nums[i] > nums[i-1] and nums[i] > nums[i+1].

Algorithm

1. Iterate over each element in the array.
2. For each element, compare it with its left and right neighbors (considering boundaries).
3. If the element is greater than both neighbors, return its index.
4. If no peak found in the loop, return 0 (covers single element case).

💡 The algorithm is straightforward but requires checking neighbors carefully, especially at boundaries.

</>

Code

def findPeakElement(nums):
    n = len(nums)
    for i in range(n):
        left = nums[i - 1] if i > 0 else float('-inf')
        right = nums[i + 1] if i < n - 1 else float('-inf')
        if nums[i] > left and nums[i] > right:
            return i
    return 0

# Example usage
if __name__ == '__main__':
    print(findPeakElement([1, 2, 3, 1]))  # Output: 2

Line Notes

n = len(nums)Store length once to avoid repeated calls

for i in range(n)Check each element sequentially

left = nums[i - 1] if i > 0 else float('-inf')Handle left boundary by assuming -∞

if nums[i] > left and nums[i] > rightCheck if current element is a peak

public class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int left = (i > 0) ? nums[i - 1] : Integer.MIN_VALUE;
            int right = (i < n - 1) ? nums[i + 1] : Integer.MIN_VALUE;
            if (nums[i] > left && nums[i] > right) {
                return i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findPeakElement(new int[]{1, 2, 3, 1})); // 2
    }
}

Line Notes

int n = nums.length;Cache array length for efficiency

for (int i = 0; i < n; i++)Iterate over all elements

int left = (i > 0) ? nums[i - 1] : Integer.MIN_VALUE;Handle left boundary with -∞

if (nums[i] > left && nums[i] > right)Check if current element is a peak

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int findPeakElement(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int left = (i > 0) ? nums[i - 1] : INT_MIN;
        int right = (i < n - 1) ? nums[i + 1] : INT_MIN;
        if (nums[i] > left && nums[i] > right) {
            return i;
        }
    }
    return 0;
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    cout << findPeakElement(nums) << endl; // 2
    return 0;
}

Line Notes

int n = nums.size();Store size once for efficiency

for (int i = 0; i < n; i++)Linear scan over all elements

int left = (i > 0) ? nums[i - 1] : INT_MIN;Use INT_MIN to simulate -∞ at left boundary

if (nums[i] > left && nums[i] > right)Check peak condition

function findPeakElement(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const left = i > 0 ? nums[i - 1] : Number.NEGATIVE_INFINITY;
        const right = i < n - 1 ? nums[i + 1] : Number.NEGATIVE_INFINITY;
        if (nums[i] > left && nums[i] > right) {
            return i;
        }
    }
    return 0;
}

// Example usage
console.log(findPeakElement([1, 2, 3, 1])); // 2

Line Notes

const n = nums.length;Cache length to avoid repeated property access

for (let i = 0; i < n; i++)Iterate through array elements

const left = i > 0 ? nums[i - 1] : Number.NEGATIVE_INFINITY;Handle left boundary as -∞

if (nums[i] > left && nums[i] > right)Check if current element is a peak

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array once, checking neighbors for each element, so time is linear. Space is constant as no extra data structures are used.

💡 For n=100,000 elements, this means 100,000 comparisons, which can be slow in interviews or large datasets.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays; it helps understand the problem before optimizing.

🧠

Modified Binary Search (Iterative)

💡 This approach uses binary search to find a peak efficiently by exploiting the property that if nums[mid] < nums[mid+1], a peak must exist on the right side, else on the left.

Intuition

If the middle element is smaller than its right neighbor, the peak lies to the right; otherwise, it lies to the left or at mid. This halves the search space each step.

Algorithm

1. Initialize low = 0 and high = n - 1.
2. While low < high, compute mid = (low + high) // 2.
3. If nums[mid] < nums[mid + 1], move low to mid + 1 (peak is right).
4. Else, move high to mid (peak is at mid or left).
5. Return low as the peak index.

💡 The key is comparing mid with mid+1 to decide which half contains a peak, reducing search space efficiently.

</>

Code

def findPeakElement(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            low = mid + 1
        else:
            high = mid
    return low

# Example usage
if __name__ == '__main__':
    print(findPeakElement([1, 2, 3, 1]))  # Output: 2

Line Notes

low, high = 0, len(nums) - 1Initialize search boundaries

while low < high:Loop until boundaries converge

mid = (low + high) // 2Find middle index

if nums[mid] < nums[mid + 1]Decide direction based on slope

public class Solution {
    public int findPeakElement(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findPeakElement(new int[]{1, 2, 3, 1})); // 2
    }
}

Line Notes

int low = 0, high = nums.length - 1;Initialize search range

while (low < high)Continue until low meets high

int mid = low + (high - low) / 2;Calculate mid safely to avoid overflow

if (nums[mid] < nums[mid + 1])Check slope direction to move boundaries

#include <iostream>
#include <vector>
using namespace std;

int findPeakElement(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < nums[mid + 1]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    cout << findPeakElement(nums) << endl; // 2
    return 0;
}

Line Notes

int low = 0, high = nums.size() - 1;Set initial search boundaries

while (low < high)Loop until boundaries converge

int mid = low + (high - low) / 2;Calculate mid index safely

if (nums[mid] < nums[mid + 1])Use slope to decide which half to keep

function findPeakElement(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (nums[mid] < nums[mid + 1]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Example usage
console.log(findPeakElement([1, 2, 3, 1])); // 2

Line Notes

let low = 0, high = nums.length - 1;Initialize binary search boundaries

while (low < high)Loop until low meets high

const mid = Math.floor((low + high) / 2);Calculate middle index

if (nums[mid] < nums[mid + 1])Compare mid with next to decide direction

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each iteration halves the search space, so time complexity is logarithmic. Space is constant as no extra data structures are used.

💡 For n=100,000, this means about 17 comparisons, which is very efficient.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and elegance.

🧠

Modified Binary Search (Recursive)

💡 This approach is a recursive version of the iterative binary search, useful to understand recursion and divide-and-conquer strategies.

Intuition

Recursively check the middle element and decide which half to search based on the slope between mid and mid+1.

Algorithm

1. Define a recursive function with low and high indices.
2. If low == high, return low as peak index.
3. Calculate mid = (low + high) // 2.
4. If nums[mid] < nums[mid + 1], recurse on right half (mid+1 to high).
5. Else recurse on left half (low to mid).

💡 The recursion breaks the problem into smaller parts, focusing on the half that must contain a peak.

</>

Code

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

# Example usage
if __name__ == '__main__':
    print(findPeakElement([1, 2, 3, 1]))  # Output: 2

Line Notes

def binarySearch(low, high):Helper recursive function with boundaries

if low == high:Base case: single element is peak

mid = (low + high) // 2Calculate middle index

if nums[mid] < nums[mid + 1]Decide which half to recurse on

public class Solution {
    public int findPeakElement(int[] nums) {
        return binarySearch(nums, 0, nums.length - 1);
    }

    private int binarySearch(int[] nums, int low, int high) {
        if (low == high) return low;
        int mid = low + (high - low) / 2;
        if (nums[mid] < nums[mid + 1]) {
            return binarySearch(nums, mid + 1, high);
        } else {
            return binarySearch(nums, low, mid);
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findPeakElement(new int[]{1, 2, 3, 1})); // 2
    }
}

Line Notes

return binarySearch(nums, 0, nums.length - 1);Start recursion with full array

if (low == high) return low;Base case: peak found

int mid = low + (high - low) / 2;Calculate mid safely

if (nums[mid] < nums[mid + 1])Choose right half if slope goes up

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int low, int high) {
    if (low == high) return low;
    int mid = low + (high - low) / 2;
    if (nums[mid] < nums[mid + 1]) {
        return binarySearch(nums, mid + 1, high);
    } else {
        return binarySearch(nums, low, mid);
    }
}

int findPeakElement(vector<int>& nums) {
    return binarySearch(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    cout << findPeakElement(nums) << endl; // 2
    return 0;
}

Line Notes

if (low == high) return low;Base case for recursion

int mid = low + (high - low) / 2;Calculate mid index safely

if (nums[mid] < nums[mid + 1])Decide which half to recurse on

return binarySearch(nums, 0, nums.size() - 1);Start recursion with full array

function findPeakElement(nums) {
    function binarySearch(low, high) {
        if (low === high) return low;
        const mid = Math.floor((low + high) / 2);
        if (nums[mid] < nums[mid + 1]) {
            return binarySearch(mid + 1, high);
        } else {
            return binarySearch(low, mid);
        }
    }
    return binarySearch(0, nums.length - 1);
}

// Example usage
console.log(findPeakElement([1, 2, 3, 1])); // 2

Line Notes

function binarySearch(low, high)Recursive helper function

if (low === high) return low;Base case: found peak

const mid = Math.floor((low + high) / 2);Calculate mid index

if (nums[mid] < nums[mid + 1])Choose right half if slope goes up

⏱

Complexity

TimeO(log n)

SpaceO(log n)

Recursion depth is logarithmic, so time is O(log n). Space is O(log n) due to recursion call stack.

💡 For n=100,000, about 17 recursive calls are made, which is efficient but uses stack space.

Interview Verdict: Accepted and optimal but uses recursion stack

This approach is elegant but may risk stack overflow on very large inputs; iterative is safer.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the modified binary search iterative approach is preferred for its efficiency and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code for large inputs
2. Modified Binary Search (Iterative)	O(log n)	O(1)	No	N/A	Code this approach for optimal solution
3. Modified Binary Search (Recursive)	O(log n)	O(log n)	Yes (deep recursion)	N/A	Good to explain recursion, but iterative preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce the binary search optimization and explain the intuition.Step 4: Code the optimal solution carefully, handling boundaries.Step 5: Test your code with edge cases and explain your test strategy.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to binary search, and correctness in handling boundaries.

Common Follow-ups

• What if the array contains duplicates? → Binary search logic needs adjustment.
• Can you find all peak elements? → Modify approach to collect all peaks.

💡 These follow-ups test your ability to adapt the solution to variations and think beyond the base problem.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to find a local maximum or minimum in an array without scanning all elements, especially when neighbors define the condition.

Signature Phrases

'An element is a peak if it is greater than its neighbors''Find a peak element and return its index'

NOT This Pattern When

Problems that require global maximum/minimum or sorting are different patterns.

Similar Problems

Find Minimum in Rotated Sorted Array - uses modified binary search to find boundaryFind Local Minimum - similar peak/valley concept with binary searchMountain Array Peak Index - peak finding in a mountain array

Practice

1. Consider the following Python function maxDistanceOptimized that finds the largest minimum distance to place m balls in sorted positions. Given position = [1, 2, 4, 8] and m = 3, what is the final returned value?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace binary search boundaries

   Initial low=1, high=7 (8-1). Mid=4: can_place(4)? Positions: 1,2,4,8. Place first ball at 1, next at 8 (8-1=7≥4), count=2 < m=3 -> False.

2. Step 2: Adjust boundaries and find final result

   high=3, mid=2: can_place(2)? Place at 1, then 4 (4-1=3≥2), then 8 (8-4=4≥2), count=3 -> True. low=3, mid=3: can_place(3)? Place at 1, then 4 (3≥3), then 8 (4≥3), count=3 -> True. low=4, high=3 ends loop. Result=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Final max minimum distance is 3 [OK]

Hint: Check feasibility at mid distances carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting balls placed in can_place

2. You are given a 2D matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. You need to determine if a target value exists in the matrix. Which approach guarantees the most efficient search in this scenario?

easy

A. Perform a binary search on each row individually to find the target.

B. Use a brute force nested loop to check every element until the target is found.

C. Start from the bottom-left corner and move only upwards or rightwards to find the target.

D. Use dynamic programming to build a table of reachable values and check for the target.

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, allowing binary search on rows.

2. Step 2: Evaluate approaches

   Brute force is O(m*n), bottom-left approach is staircase search but not binary search, DP is unrelated here. Binary search on each row yields O(m*log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on rows exploits sorted rows efficiently [OK]

Hint: Sorted rows allow binary search per row [OK]

Common Mistakes:

• Confusing staircase search with binary search on rows
• Assuming DP applies here
• Thinking brute force is optimal

3. What is the time complexity of the optimal approach that uses a single binary search followed by expanding boundaries to find the first and last positions of the target in a sorted array?

medium

A. O(n)

B. O(log n + k), where k is the number of occurrences of the target

C. O(log n * k), where k is the number of occurrences of the target

D. O(log n)

Solution

1. Step 1: Analyze binary search phase

   Binary search runs in O(log n) to find one occurrence of target.

2. Step 2: Analyze boundary expansion phase

   Expanding left and right to find all occurrences takes O(k), where k is count of target.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Combined complexity is O(log n + k), not multiplicative [OK]

Hint: Binary search plus linear expansion over occurrences [OK]

Common Mistakes:

• Assuming O(log n) only
• Multiplying log n by k incorrectly
• Ignoring expansion cost

4. What is the time complexity of the optimal approach that performs binary search on each row of an m x n matrix to find a target value?

medium

A. O(log m * log n)

B. O(m * n)

C. O(m * log n)

D. O(m + n)

Solution

1. Step 1: Identify outer loop complexity

   We iterate over m rows, so outer loop is O(m).

2. Step 2: Identify inner binary search complexity

   Binary search on each row of length n takes O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(m * log n), not O(m*n) or O(log m * log n) [OK]

Hint: Binary search is logarithmic per row [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Thinking binary search applies to columns too
• Assuming double log complexity

5. Suppose the 2D matrix is no longer guaranteed to have each row's first element greater than the last element of the previous row, but each row is still sorted individually. Which approach correctly finds the target with the best average time complexity?

hard

A. Treat the matrix as a 1D sorted array and apply binary search.

B. Use a min-heap to merge rows and search for the target.

C. Use a brute force nested loop to scan all elements.

D. Perform binary search on each row independently until the target is found.

Solution

1. Step 1: Analyze matrix ordering

   Rows are sorted but no global ordering between rows, so flattening as 1D sorted array is invalid.

2. Step 2: Identify correct search method

   Binary searching each row independently leverages row-wise sorting, yielding O(m log n) average time.

3. Step 3: Evaluate other options

   Brute force is O(m*n), min-heap merging is unnecessary overhead, and 1D binary search is incorrect due to lack of global order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Row-wise binary search works without global ordering [OK]

Hint: Global ordering is required for 1D binary search; otherwise search each row separately [OK]

Common Mistakes:

• Applying 1D binary search without global order
• Ignoring row-wise binary search
• Using brute force unnecessarily