Identify Local Maxima — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Identify Local Maxima problem optimally.
O(n)O(1)Problem Description
Given an array of distinct integers, return all elements that are strictly greater than each of their immediate neighbors. For the first element only the right neighbor is considered, for the last element only the left neighbor, and for any middle element both adjacent values must be smaller. Preserve the original order of appearance in the output.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Identify Local Maxima"
WHY DOES IT MATTER?
Identifying local maxima is a building block for peak‑finding, signal processing, and performance‑monitoring tasks where you need to detect spikes without extra memory overhead.
OPTIMIZATION CHALLENGE
The insight is that a constant‑size sliding window lets you decide the answer for the centre element using only O(1) work, eliminating the need for nested loops or auxiliary heaps.
REAL-WORLD CONNECTION
In distributed monitoring systems, each node reports a metric; a node whose metric exceeds both its immediate predecessor and successor in time can be considered a spike, analogous to a local maximum in an array.
During an interview, write the loop that handles the first, middle, and last elements separately or use a sentinel trick; this avoids index‑out‑of‑bounds bugs and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
In an array of distinct integers, a local maximum is an element that is larger than its immediate neighbors. A naïve solution would compare each element with its neighbors using nested loops or recompute comparisons, leading to O(n) time but potentially O(n) extra space if auxiliary structures are used, and more importantly, it may miss edge‑case handling when the array size is 1 or 2. The optimal paradigm leverages a single linear scan: for each index i we only need to look at A[i‑1] and A[i+1] (when they exist). Because each element is examined a constant number of times, the algorithm runs in Θ(n) time and O(1) auxiliary space, which is optimal since any algorithm must inspect every element at least once to decide whether it is a local maximum. The problem is a special case of the sliding‑window maximum where the window size is three. By fixing the window and moving it one step at a time, we can decide in O(1) per step whether the centre of the window is a local maximum. This viewpoint clarifies why no additional data structures such as heaps or deques are required: the window is constant‑size, so the maximum can be obtained by direct comparison. Consequently, the solution is both time‑optimal and space‑optimal, matching the lower bound for any comparison‑based algorithm on an unsorted array.
Interview Questions on This Problem
Q1How would you modify the algorithm to return the indices of local maxima instead of the values?
Store the current index i when A[i] satisfies the local‑maximum condition; the rest of the logic stays identical, still O(n) time and O(1) extra space.
Q2What changes are needed if the array may contain duplicate values and we define a local maximum as greater than or equal to its neighbors?
Replace the strict > comparisons with >= for both sides; edge handling remains the same and the algorithm still runs in O(n) time, but you must ensure equal neighbors are treated correctly to avoid false positives.
Q3Can you solve the problem in a single pass without using extra space when the input is provided as a stream?
Yes, keep the previous two elements in variables; when the middle element becomes the previous one, compare it with its left neighbor (stored) and the newly read right neighbor. Emit it if it is larger. This yields O(1) space and O(n) time for a streaming input.
Examples
Input
[1,3,2,5,4]
Output
[3,5]
Explanation: Element 1 is not greater than its right neighbor 3. Element 3 > 1 and > 2, so it is a local maximum. Element 2 fails. Element 5 > 2 and > 4, so it is a local maximum. Element 4 is the last element but 4 < 5, so it is excluded.
Input
[10,5,6,2]
Output
[10,6]
Explanation: First element 10 has only right neighbor 5 and 10>5, so it qualifies. Element 5 is smaller than both neighbors. Element 6 >5 and >2, so it qualifies. Last element 2 is smaller than 6, so it does not qualify.
Input
[7]
Output
[7]
Explanation: With a single element there are no neighbors, therefore it trivially satisfies the condition and is returned.
Constraints
- 1 <= arr.length <= 100000
- All elements in arr are distinct
- -1000000000 <= arr[i] <= 1000000000
Optimal Approach & Strategy
Traverse the array once, comparing each element only with its immediate neighbors, achieving O(n) time and O(1) extra space.
Brute Force Approach
Check every element against all other elements or recompute neighbor comparisons in nested loops, leading to O(n²) time.
Code Solutions
function findLocalMaxima(arr) {
const res = [];
const n = arr.length;
for (let i = 0; i < n; ++i) {
const leftOk = (i === 0) || (arr[i] > arr[i-1]);
const rightOk = (i === n-1) || (arr[i] > arr[i+1]);
if (leftOk && rightOk) res.push(arr[i]);
}
return res;
}
// Driver (same as template)
function main(){
const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0) return;
const n=input[0];
const arr=input.slice(1,1+n);
const res=findLocalMaxima(arr);
console.log(res.join(' '));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<int> findLocalMaxima(const vector<int>& arr) {
vector<int> res;
int n = arr.size();
for (int i = 0; i < n; ++i) {
bool leftOk = (i == 0) || (arr[i] > arr[i-1]);
bool rightOk = (i == n-1) || (arr[i] > arr[i+1]);
if (leftOk && rightOk) res.push_back(arr[i]);
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> a(n); for(int i=0;i<n;++i)cin>>a[i];
vector<int> ans=findLocalMaxima(a);
for(size_t i=0;i<ans.size();++i){if(i)cout<<' ';cout<<ans[i];}
cout<<'\n';
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static List<Integer> findLocalMaxima(int[] arr) {
List<Integer> res = new ArrayList<>();
int n = arr.length;
for (int i = 0; i < n; ++i) {
boolean leftOk = (i == 0) || (arr[i] > arr[i-1]);
boolean rightOk = (i == n-1) || (arr[i] > arr[i+1]);
if (leftOk && rightOk) res.add(arr[i]);
}
return res;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
int idx = 0;
while (idx < n) {
if (!st.hasMoreTokens()) {
line = br.readLine();
if (line == null) break;
st = new StringTokenizer(line);
continue;
}
arr[idx++] = Integer.parseInt(st.nextToken());
}
List<Integer> res = findLocalMaxima(arr);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(res.get(i));
}
System.out.println(sb.toString());
}
}def find_local_maxima(arr):
res = []
n = len(arr)
for i in range(n):
left_ok = (i == 0) or (arr[i] > arr[i-1])
right_ok = (i == n-1) or (arr[i] > arr[i+1])
if left_ok and right_ok:
res.append(arr[i])
return res
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
n = int(data[0])
arr = list(map(int, data[1:1+n]))
ans = find_local_maxima(arr)
print(' '.join(map(str, ans)))function findLocalMaxima(arr) {
const res = [];
const n = arr.length;
for (let i = 0; i < n; ++i) {
const leftOk = (i === 0) || (arr[i] > arr[i-1]);
const rightOk = (i === n-1) || (arr[i] > arr[i+1]);
if (leftOk && rightOk) res.push(arr[i]);
}
return res;
}
// Driver (same as template)
function main(){
const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0) return;
const n=input[0];
const arr=input.slice(1,1+n);
const res=findLocalMaxima(arr);
console.log(res.join(' '));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.