Find Peak Element

📋

Problem

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.

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

Edge cases: Single element array → index 0Strictly increasing array → last index is peakStrictly decreasing array → first index is peak

</>

IDE

def findPeakElement(nums: list[int]) -> int:public int findPeakElement(int[] nums)int findPeakElement(vector<int>& nums)function findPeakElement(nums)

def findPeakElement(nums):
    # Write your solution here
    pass

class Solution {
    public int findPeakElement(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findPeakElement(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findPeakElement(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning first index without checking if it is a peak.✅ Check if nums[0] > nums[1] before returning 0; otherwise, use binary search to find a valid peak.

Wrong: 1Returning mid index without verifying it is a peak (not checking neighbors).✅ Before returning mid, verify nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1] (handle boundaries).

Wrong: 9Off-by-one error causing index out of range or incorrect peak detection.✅ Use mid = left + (right - left) // 2 and carefully check mid+1 index within bounds.

Wrong: Algorithm times out due to linear scan on large input.✅ Implement binary search approach to achieve O(log n) time complexity.

✓

Test Cases

Focus on handling arrays with minimal or maximal length and boundary peaks.

Beware of common pitfalls like greedy choices and off-by-one errors in binary search.

Optimize your solution to use binary search for logarithmic time complexity.

t1_01basic

Input{"nums":[1,2,3,1]}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Think about comparing middle elements with neighbors to find a peak.

💡 Use modified binary search to check if mid element is greater than neighbors.

💡 If nums[mid] < nums[mid+1], move right; else move left or return mid.

Why it failed: Returned index is not a peak or out of bounds. Fix by ensuring returned index satisfies nums[i] > nums[i-1] and nums[i] > nums[i+1] (handle boundaries).

✓ Correctly identified a peak index matching the canonical example.

t1_02basic

Input{"nums":[1,3,2,4,1]}

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Peaks can be anywhere, not necessarily unique; check neighbors carefully.

💡 Binary search can find any peak by comparing mid with mid+1.

💡 If nums[mid] > nums[mid+1], peak is at mid or left; else right.

Why it failed: Returned index is not a peak. Fix by verifying nums[i] > neighbors before returning index.

✓ Correctly found a valid peak index different from canonical example.

t2_01edge

Input{"nums":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Single element array; the only element is the peak by definition.

💡 Consider arrays with only one element.

💡 A single element is always a peak since neighbors are -∞.

💡 Return index 0 immediately if array length is 1.

Why it failed: Fails to handle single element arrays, returning invalid index or error. Fix by adding base case for length 1 returning 0.

✓ Correctly handles single element arrays by returning index 0.

t2_02edge

Input{"nums":[1,2,3,4,5]}

Expected4

⏱ Performance - must finish in 2000ms

Strictly increasing array; last element is peak since nums[n] = -∞.

💡 Check behavior on strictly increasing sequences.

💡 Peak must be at the right boundary if array is strictly increasing.

💡 Return last index if nums[last] > nums[last-1].

Why it failed: Fails to identify peak at right boundary in strictly increasing array. Fix by checking boundary conditions explicitly.

✓ Correctly identifies last element as peak in strictly increasing array.

t2_03edge

Input{"nums":[5,4,3,2,1]}

Expected0

⏱ Performance - must finish in 2000ms

Strictly decreasing array; first element is peak since nums[-1] = -∞.

💡 Check behavior on strictly decreasing sequences.

💡 Peak must be at the left boundary if array is strictly decreasing.

💡 Return index 0 if nums[0] > nums[1].

Why it failed: Fails to identify peak at left boundary in strictly decreasing array. Fix by checking boundary conditions explicitly.

✓ Correctly identifies first element as peak in strictly decreasing array.

t3_01corner

Input{"nums":[1,3,2,4,3,5,4]}

Expected1

⏱ Performance - must finish in 2000ms

Multiple peaks exist; index 1 (3) is a valid peak.

💡 Beware of greedy approach that always picks first peak found.

💡 Binary search must correctly handle multiple peaks by checking neighbors.

💡 Check both sides of mid to decide search direction, not just first peak.

Why it failed: Greedy approach returns first local peak without checking if better peak exists. Fix by using binary search comparing mid and mid+1 to decide direction.

✓ Correctly handles multiple peaks by returning a valid peak index.

t3_02corner

Input{"nums":[1,2,1,3,5,6,4]}

Expected5

⏱ Performance - must finish in 2000ms

Peak at index 5 (6) is valid; tests correct boundary handling in binary search.

💡 Check off-by-one errors in binary search boundaries.

💡 Ensure mid calculation and comparisons do not skip valid peaks.

💡 Use mid = left + (right - left) // 2 and compare nums[mid] with nums[mid+1].

Why it failed: Off-by-one error causes missing peak at boundary. Fix by careful mid calculation and boundary checks.

✓ Correctly finds peak near array boundary without off-by-one errors.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7,8,9,10]}

Expected9

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 indexing or off-by-one in binary search; last element is peak.

💡 Confirm indexing is zero-based and consistent.

💡 Check that comparisons use correct indices for neighbors.

💡 Return last index if nums[last] > nums[last-1], no off-by-one errors.

Why it failed: Confuses 0/1 indexing causing invalid index or wrong peak. Fix by consistent zero-based indexing and neighbor checks.

✓ Handles indexing correctly and returns valid peak index.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(log n) binary search must complete within 2 seconds; brute force O(n) also feasible but slower.

💡 Use binary search to achieve O(log n) time complexity.

💡 Avoid linear scans that cause timeouts on large inputs.

💡 Compare nums[mid] and nums[mid+1] to decide search direction.

Why it failed: Algorithm exceeds time limit due to O(n) or worse complexity. Fix by implementing O(log n) binary search approach.

✓ Algorithm runs within time limit using O(log n) binary search.

Practice

1. Consider the following buggy code snippet intended to find the first and last positions of a target in a sorted array. What is the bug?

medium

A. The binary search stops immediately after finding any occurrence, not the first or last

B. The initial values of start and end are incorrectly set

C. The mid calculation can cause overflow for large indices

D. The while loops expanding boundaries do not check array bounds before accessing indices

Solution

1. Step 1: Examine boundary expansion loops

   Loops check nums[start - 1] and nums[end + 1] without verifying indices are within array bounds.

2. Step 2: Identify potential index out of range error

   If start=0 or end=len(nums)-1, accessing start-1 or end+1 causes IndexError.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary checks missing before array access [OK]

Hint: Always check array bounds before accessing neighbors [OK]

Common Mistakes:

• Stopping binary search early
• Ignoring boundary checks
• Incorrect mid calculation

2. The following code attempts to find the maximum minimum distance to place m balls in position. Identify the bug that causes incorrect results or infinite loops.

medium

A. Not stopping early in can_place after placing all balls

B. Incorrect binary search boundaries: low should start at 0

C. Returning result before binary search loop ends

D. Line missing position.sort() before feasibility check

Solution

1. Step 1: Check sorting necessity

   The feasibility check assumes positions are sorted to place balls greedily. Missing position.sort() breaks this assumption.

2. Step 2: Consequences of missing sort

   Without sorting, the greedy check may fail to place balls correctly, causing wrong feasibility results and incorrect final answer.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting is essential before greedy feasibility check [OK]

Hint: Positions must be sorted before greedy feasibility check [OK]

Common Mistakes:

• Forgetting to sort positions
• Incorrect binary search boundaries causing infinite loops

3. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility

4. What is the time complexity of the optimal binary search solution for finding the minimum speed to arrive on time, given n distances and a precision epsilon for floating point speed search?

medium

A. O(log n * (maxSpeed / epsilon))

B. O(n * maxSpeed)

C. O(n^2 * log(maxSpeed))

D. O(n * log((maxSpeed - minSpeed) / epsilon))

Solution

1. Step 1: Identify the binary search iterations

   Binary search on speed range [minSpeed, maxSpeed] with precision epsilon takes O(log((maxSpeed - minSpeed)/epsilon)) steps.

2. Step 2: Calculate per-iteration cost

   Each feasibility check sums over n distances, so O(n) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining steps yields O(n log((maxSpeed - minSpeed)/epsilon)) [OK]

Hint: Binary search iterations times linear feasibility check [OK]

Common Mistakes:

• Confusing maxSpeed with n
• Ignoring epsilon precision in log factor

5. What is the time complexity of the iterative fast exponentiation algorithm for computing x^n where n is a 32-bit integer?

medium

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

Solution

1. Step 1: Identify loop iterations

   The algorithm halves n each iteration, so the loop runs approximately log₂(n) times.

2. Step 2: Confirm work per iteration

   Each iteration does a constant number of multiplications and divisions, so total time is O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Halving exponent each step -> logarithmic time [OK]

Hint: Halving exponent means O(log n) time [OK]

Common Mistakes:

• Confusing with O(n) from naive multiplication
• Assuming O(1) due to constant ops per iteration
• Thinking recursion adds extra complexity