What is the brute force approach and complexity for Find Peak Element?

Scan left to right; the first i with nums[i] > nums[i+1] is a peak with time complexity O(N) and space complexity O(1).

What is the optimal approach and complexity for Find Peak Element?

If nums[mid] < nums[mid+1], a peak is to the right → lo = mid + 1; else hi = mid with optimal time complexity O(log N) and space complexity O(1).

Find Peak Element

Q: What is the optimal approach and complexity for Find Peak Element?

If nums[mid] < nums[mid+1], a peak is to the right → lo = mid + 1; else hi = mid with optimal time complexity O(log N) and space complexity O(1).

Q: How do you identify the pattern for Find Peak Element?

Look for key signals in the prompt: "return any peak" indicates You don't need all peaks or the biggest one — just one. That's what lets you ignore half the array.; "nums[−1] = nums[n] = −∞" indicates Guarantees a peak exists, and that climbing in any direction must end at one.; "neighbours are never equal" indicates The slope at every point is clearly up or down — the yes/no question always has an answer.; "O(log n)" indicates Binary search, even though the array is not sorted..

Medium·LeetCode #162 Pro OnlyMedium

LeetCode

Problem Statement

A peak is an element that is strictly bigger than both of its neighbours.

You are given an array nums. Return the index of any peak — if there are several, any one is accepted.

Pretend there is a value of −∞ just before the array and just after it (nums[−1] = nums[n] = −∞). So the first element only has to beat its right neighbour, and the last only has to beat its left neighbour. Two neighbours are never equal.

Your solution must run in O(log n) time.

Input

An integer array nums where nums[i] != nums[i + 1] for every valid i.

Output

The index of any peak element.

Example 1

Input: nums = [1, 2, 3, 1]

Output: 2

3 is bigger than 2 on its left and 1 on its right.

Example 2

Input: nums = [1, 2, 1, 3, 5, 6, 4]

Output: 5 (1 is also accepted)

Index 1 (value 2) is a peak, and index 5 (value 6) is a peak. Returning either one is correct.

Example 3

Input: nums = [1, 2, 3, 4]

Output: 3

The values only climb. The last element 4 beats 3, and after it comes −∞, so it is a peak.

Constraints

• 1 ≤ n ≤ 1000
• −2^31 ≤ nums[i] ≤ 2^31 − 1
• nums[i] != nums[i + 1] for all valid i

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“return any peak”

→ You don't need all peaks or the biggest one — just one. That's what lets you ignore half the array.

“nums[−1] = nums[n] = −∞”

→ Guarantees a peak exists, and that climbing in any direction must end at one.

“neighbours are never equal”

→ The slope at every point is clearly up or down — the yes/no question always has an answer.

“O(log n)”

→ Binary search, even though the array is not sorted.

Approach Complexity Ladder

Brute Force — walk until the path goes downO(N)O(1)

Scan left to right; the first i with nums[i] > nums[i+1] is a peak

Optimal — binary search on the slopeO(log N)O(1)

If nums[mid] < nums[mid+1], a peak is to the right → lo = mid + 1; else hi = mid

Brute Force Intuition

Walk from the left. Since nums[−1] = −∞, the first element beats its left side. As long as the next value is bigger, keep walking. The first time the next value is smaller, you are on a peak. If that never happens, the last element is a peak.

Recognition rule for this sub-pattern:

Array is not fully sorted, but one half always is. Decide which half is sorted, then which half holds the answer.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Search in Rotated Sorted Array Search in Rotated Sorted Array II