Find Peak Element

easyPROSearch & SortGoogle DSA

A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element and return its index.

You may assume nums[-1] = nums[n] = -infinity. If there are multiple peaks, return the index of any one.

Example

Input

1,2,3,1

Output

Reasoning

The input nums holds $n = 4$ integers, $1, 2, 3, 1$ , at indices $0$ to $3$ . Treat each end as bordered by $-\infty$ , so edge elements also have two neighbours to beat.
Writing $x_i$ for the value at index $i$ , a peak needs $x_{i-1} < x_i > x_{i+1}$ , strict on both sides.
Index $0$ : $1 < 2$ , so the value $1$ loses to its right neighbour. Index $1$ : $2 < 3$ , so it loses too. Index $3$ : $1 < 3$ , so it loses to its left neighbour.
Index $2$ : $2 < 3 > 1$ , so the value $3$ beats both neighbours. It is the only peak here, and the output is its index 2, not the value $3$ .
Notice that a peak always exists: the values rise from $1$ to $3$ and then fall, and since adjacent values are never equal, the place where the rise turns into a fall must be a peak. With the $-\infty$ borders, even a strictly increasing list has one: its last element.

Constraints

1 <= len(nums) <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] != nums[i + 1] for all valid i

Learn this in

Binary SearchDSA Study Plan

More from Google DSA

Time Based Key-Value Storemedium Moving Average from Data Streameasy Snapshot Arraymedium LRU Cachemedium Search in Rotated Sorted Arraymedium

Concept primerPREVIEW

Background Knowledge

The "Find Peak Element" problem is a classic example of a search problem, where we need to find a specific element in an array that satisfies certain conditions. In this case, we're looking for a peak element, which is an element that is strictly greater than its neighbors. This problem can be solved using various approaches, including iterative and recursive methods. To understand this problem, it's essential to have a basic understanding of array data structures and comparative analysis.

The concept of a peak element is crucial in this problem. A peak element is not necessarily the maximum element in the array, but rather an element that is greater than its immediate neighbors. This means that we need to compare each element with its neighbors to determine if it's a peak element. We can assume that the array is bounded by negative infinity on both ends, which simplifies the problem by eliminating the need to handle edge cases.

The "Find Peak Element" problem is also related to the concept of local maxima, which is a point in an array where the value is greater than its neighbors. In this case, we're looking for a local maximum that is strictly greater than its neighbors. This problem requires a combination of logical reasoning and algorithmic thinking to solve efficiently.

Algorithm/Approach

The general approach to solve this problem is to use a binary search algorithm, which is a divide-and-conquer technique that allows us to find an element in an array by repeatedly dividing the search interval in half. In this case, we can use a modified binary search algorithm to find a peak element in the array. The key idea is to compare the middle element with its neighbors and determine which half of the array is more likely to contain a peak element.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results