Local Maxima Indices — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Local Maxima Indices problem optimally.
O(n)O(1)Problem Description
Given an integer array radiation_intensities, return a list of all positions i (0‑based) where radiation_intensities[i] is greater than or equal to its immediate left neighbor (if i>0) and greater than or equal to its immediate right neighbor (if i< n‑1). The returned indices must be in ascending order. The algorithm should run in linear time and use only constant extra space beyond the output.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Local Maxima Indices"
WHY DOES IT MATTER?
This pattern is essential because it teaches the fundamental skill of linear scanning with local state. Many real-world problems, such as detecting peaks in time-series data, identifying outliers in sensor readings, or finding local optima in optimization landscapes, rely on comparing an element to its immediate neighbors. Mastering this pattern builds the foundation for more complex sliding window and two-pointer techniques.
OPTIMIZATION CHALLENGE
The key insight is that the condition for a local maximum at index i depends only on i-1, i, and i+1. This locality allows for a single-pass solution where we maintain a constant amount of state (the current and previous values) rather than storing the entire array or using a heap. The challenge is correctly handling the boundary conditions at the start and end of the array, where one neighbor is missing.
REAL-WORLD CONNECTION
Consider a stock trading algorithm that identifies 'local peaks' in price data to signal potential sell points. The algorithm scans the price history linearly, comparing each day's closing price to the previous and next day's prices. This is a direct application of local maxima detection, where the 'radiation intensities' are stock prices, and the indices are the days when a local peak occurred.
In an interview, explicitly state your boundary conditions before coding. Mention that you will handle index 0 and index n-1 separately or with a unified condition that checks for the existence of neighbors. This demonstrates attention to detail and prevents off-by-one errors, which are the most common source of bugs in this type of problem.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of identifying local maxima in a linear array is a classic application of the single-pass scanning paradigm. A local maximum at index i is defined by the condition that the value at i is greater than or equal to its immediate neighbors. For boundary elements (indices 0 and n-1), the condition simplifies to being greater than or equal to their single existing neighbor. This definition ensures that plateaus (consecutive equal values) are handled correctly, as every element in a plateau satisfies the 'greater than or equal' condition relative to its neighbors within the plateau and the boundaries.
Interview Questions on This Problem
Q1How would you modify this algorithm to find strict local maxima (where the element must be strictly greater than neighbors) and how does that affect the handling of plateaus?
To find strict local maxima, change the comparison operators from '>=' to '>'. This fundamentally changes the behavior for plateaus: in a sequence of equal values, no element will be a strict local maximum because none are strictly greater than their neighbors. The algorithm remains O(n) time and O(1) space, but the logic for boundary conditions and internal elements must strictly enforce the inequality.
Q2If the array is extremely large and stored in a distributed system where accessing an element requires a network call, how would you optimize the access pattern?
In a distributed context, random access is expensive. However, since this is a linear scan, we can process the array in chunks or streams. We would buffer a small window of elements (e.g., 3 elements) to evaluate the local maximum condition for the middle element. This reduces the number of network round-trips by allowing us to evaluate multiple indices with a single batch fetch, effectively turning the problem into a streaming window problem with a fixed window size of 3.
Q3What is the time complexity if you were to use a divide-and-conquer approach to find all local maxima, and why is the linear scan preferred?
A divide-and-conquer approach would typically involve splitting the array, finding local maxima in each half, and then checking the boundary between the halves. This would result in O(n log n) time complexity due to the recursion overhead and repeated boundary checks. The linear scan is preferred because it achieves O(n) time with O(1) extra space, which is optimal for this problem since every element must be inspected at least once to determine if it is a local maximum.
Examples
Input
[3,5,4,4,6,2]
Output
[1,4]
Explanation: Index 1 holds 5, which is ≥3 (left) and ≥4 (right). Index 4 holds 6, which is ≥4 (left) and ≥2 (right). No other index satisfies both conditions.
Input
[7,7,7]
Output
[0,1,2]
Explanation: All elements are equal, so each element is ≥ its neighbors (or the only neighbor for the ends). Hence every index is a local maximum.
Input
[1,3,2,5,5,4,6]
Output
[1,3,4,6]
Explanation: Index 1:3≥1 and ≥2. Index 3:5≥2 and ≥5. Index 4:5≥5 and ≥4. Index 6:6≥4 (right side absent). Other positions fail at least one side.
Constraints
- 1 <= radiation_intensities.length <= 200000
- -1000000000 <= radiation_intensities[i] <= 1000000000
- Solution must run in O(n) time
- Only O(1) additional memory besides the output is allowed
Optimal Approach & Strategy
The optimal approach is a single pass through the array, checking the local maximum condition for each element by comparing it to its immediate neighbors. This runs in O(n) time and uses O(1) extra space, as we only need to store the current index and the resulting list of indices.
Brute Force Approach
A naive approach might involve nested loops where for each index, you scan the entire array to find its neighbors, which is inefficient and unnecessary. This would result in O(n^2) time complexity, which is suboptimal for large inputs.
Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++] || 0;
const arr = data.slice(p, p + n);
function localMaximaIndices(a){
const res = [];
for(let i=0;i<a.length;i++){
const leftOk = (i===0) || (a[i] >= a[i-1]);
const rightOk = (i===a.length-1) || (a[i] >= a[i+1]);
if(leftOk && rightOk) res.push(i);
}
return res;
}
const result = localMaximaIndices(arr);
console.log(result.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> localMaximaIndices(const vector<int>& a) {
vector<int> ans;
int n = a.size();
for(int i=0;i<n;++i){
bool left_ok = (i==0) || (a[i] >= a[i-1]);
bool right_ok = (i==n-1) || (a[i] >= a[i+1]);
if(left_ok && right_ok) ans.push_back(i);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> arr(n);
for(int i=0;i<n;++i) cin>>arr[i];
vector<int> res = localMaximaIndices(arr);
for(size_t i=0;i<res.size();++i){
if(i) cout << ' ';
cout << res[i];
}
cout << '\n';
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static List<Integer> localMaximaIndices(int[] a) {
List<Integer> res = new ArrayList<>();
int n = a.length;
for(int i=0;i<n;i++){
boolean leftOk = (i==0) || (a[i] >= a[i-1]);
boolean rightOk = (i==n-1) || (a[i] >= a[i+1]);
if(leftOk && rightOk) res.add(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;
int n = Integer.parseInt(line.trim());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
List<Integer> res = localMaximaIndices(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());
}
}import sys
def local_maxima_indices(a):
res = []
n = len(a)
for i in range(n):
left_ok = (i == 0) or (a[i] >= a[i-1])
right_ok = (i == n-1) or (a[i] >= a[i+1])
if left_ok and right_ok:
res.append(i)
return res
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
arr = list(map(int, data[1:1+n]))
res = local_maxima_indices(arr)
print(' '.join(map(str, res)))
if __name__ == "__main__":
main()const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++] || 0;
const arr = data.slice(p, p + n);
function localMaximaIndices(a){
const res = [];
for(let i=0;i<a.length;i++){
const leftOk = (i===0) || (a[i] >= a[i-1]);
const rightOk = (i===a.length-1) || (a[i] >= a[i+1]);
if(leftOk && rightOk) res.push(i);
}
return res;
}
const result = localMaximaIndices(arr);
console.log(result.join(' '));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.