Find the Peaks — Solution in Python, Java & C++
Find the Peaks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and enumeration.
Find the Peaks is an easy coding problem on arrays and enumeration, asked in TCS and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Enumeration
- Asked at: TCS, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array mountain of heights. An index i is a peak when mountain[i] is strictly greater than both of its neighbours.
The first and last indices are never peaks — they have only one neighbour. Return every peak index in increasing order.
Example 1
Input: mountain = [2,4,4]
Output: []
Explanation: Index 1 is not a peak because 4 is not strictly greater than the 4 on its right.
Example 2
Input: mountain = [1,4,3,8,5]
Output: [1,3]
Explanation: 4 beats 1 and 3; 8 beats 3 and 5. Indices 0 and 4 are excluded by the rule.
Example 3
Input: mountain = [5,5,5,5]
Output: []
Constraints
3 <= mountain.length <= 1001 <= mountain[i] <= 100
Hints for Find the Peaks
Hint 1
The definition is purely local — one index only ever needs its two neighbours.
Hint 2
Loop
ifrom1ton - 2so the neighbour lookups are always in range.Hint 3
>and not>=: a plateau is not a peak.
How to solve Find the Peaks
A peak is a local condition, so a single sweep that never touches the two ends answers the whole question.
Approach
- Run
ifrom1up ton - 2inclusive. - Record
iwhenmountain[i] > mountain[i - 1]andmountain[i] > mountain[i + 1]. - Return the recorded indices; the loop order already makes them increasing.
Why it works
Restricting the loop to the interior is the statement's own rule that the endpoints cannot qualify, and testing both neighbours is the definition verbatim, so nothing is missed and nothing extra is reported.
Complexity
- Time —
O(n) - Space —
O(1) beyond the output
Pitfalls
- Using
>=turns a flat run such as[2,4,4]into a false peak. - Looping from
0or ton - 1reads out of bounds — or, worse, silently reads a default value.
Reference solution
Python
from typing import List
def findPeaks(mountain: List[int]) -> List[int]:
out = []
for i in range(1, len(mountain) - 1):
if mountain[i] > mountain[i - 1] and mountain[i] > mountain[i + 1]:
out.append(i)
return outJava
public static int[] findPeaks(int[] mountain) {
List<Integer> out = new ArrayList<>();
for (int i = 1; i + 1 < mountain.length; i++) {
if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) out.add(i);
}
int[] res = new int[out.size()];
for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
return res;
}C++
vector<int> findPeaks(vector<int>& mountain) {
vector<int> out;
for (int i = 1; i + 1 < (int) mountain.size(); i++) {
if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) out.push_back(i);
}
return out;
}JavaScript
var findPeaks = function(mountain) {
var out = [];
for (var i = 1; i + 1 < mountain.length; i++) {
if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) out.push(i);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays