Peak Signals in Modified Array — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Peak Signals in Modified Array problem optimally.
O(N)O(N)Problem Description
Given an integer array signalStrengths of length N, first construct a new array modified of the same length. For each position i: • If i is the first element (i=0), set modified[0]=signalStrengths[1] (the only existing neighbour). • If i is the last element (i=N‑1), set modified[N‑1]=signalStrengths[N‑2]. • Otherwise set modified[i]=signalStrengths[i‑1]*signalStrengths[i+1]. After the transformation, a peak index i is one where modified[i] is not smaller than any of its existing neighbours in modified (for interior positions compare with both sides, for the ends compare with the single neighbour). Return all peak indices in increasing order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Peak Signals in Modified Array"
WHY DOES IT MATTER?
Understanding local‑dependency patterns lets you replace nested loops with constant‑time neighbour look‑ups, a skill that dramatically improves performance for large‑scale data processing tasks.
OPTIMIZATION CHALLENGE
The key insight is that each output element depends only on two known inputs; therefore you can compute it on the fly during a single traversal, avoiding repeated scans of the array.
REAL-WORLD CONNECTION
In signal‑processing pipelines, each sample often depends on its immediate neighbours (e.g., smoothing filters). Computing a transformed signal by looking at adjacent samples mirrors the same O(N) pattern used here.
During an interview, write the boundary cases first (i=0 and i=N‑1) – they are easy to get wrong. Then loop over the interior indices; this clear separation prevents off‑by‑one bugs and shows structured thinking.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
The transformation described is a classic example of a one‑pass neighbor‑product computation. For each index we need information about its immediate left and right neighbours, which can be accessed in constant time if we iterate sequentially. A naive solution might recompute products by scanning the whole array for each position, leading to O(N^2) time – infeasible for N up to 10^5 or more. The optimal paradigm leverages the fact that the required neighbours are already present in the original array, so a single linear scan suffices. By handling the boundary cases separately (first and last elements have only one neighbour), we avoid out‑of‑bounds checks and keep the algorithm simple and cache‑friendly.
Because the output size is the same as the input, the problem also illustrates the in‑place vs. out‑of‑place trade‑off. While we could overwrite the original array if it is no longer needed, most interview settings expect a new array to preserve input integrity, resulting in O(N) auxiliary space. The overall approach demonstrates how recognizing local dependencies transforms a potentially quadratic problem into a linear one, a recurring theme in array‑based interview questions.
Interview Questions on This Problem
Q1How would you compute the modified array in a single pass without using extra space beyond the output array?
Iterate i from 0 to N‑1; for i==0 set result[0]=arr[1]; for i==N‑1 set result[N‑1]=arr[N‑2]; otherwise result[i]=arr[i‑1]*arr[i+1]; This uses only the original array for look‑ups and O(1) extra variables.
Q2If the input array can contain zeros, does the algorithm need any special handling?
No special handling is required because multiplication with zero naturally yields zero; the algorithm still runs in O(N) time and correctly reflects the product of neighbours, even when one or both neighbours are zero.
Q3How would you adapt the solution if you were asked to return the sum of all values in the modified array instead of the array itself?
Maintain a running sum variable while iterating; for each index compute the neighbour product as before and add it to the sum. This eliminates the need to store the entire result, reducing space to O(1).
Examples
Input
[2,3,4,5]
Output
[2]
Explanation: modified[0]=3, modified[1]=2*4=8, modified[2]=3*5=15, modified[3]=4 → modified=[3,8,15,4]. Index 2 has value 15 which is >=8 and >=4, so it is the only peak.
Input
[7,1,7,1,7]
Output
[1,3]
Explanation: modified=[1,7*7=49,1*1=1,7*7=49,1] → [1,49,1,49,1]. Indices 1 and 3 have value 49 which is >= both neighbours, thus they are peaks.
Input
[0,-2,3,-4,5,-6]
Output
[4]
Explanation: modified[0]=-2, modified[1]=0*3=0, modified[2]=-2*-4=8, modified[3]=3*5=15, modified[4]=-4*-6=24, modified[5]=5 → [-2,0,8,15,24,5]. Only index 4 (value 24) is >= its neighbours 15 and 5, so it is the sole peak.
Constraints
- 1 <= signalStrengths.length <= 100000
- -1000000000 <= signalStrengths[i] <= 1000000000
- Solution must run in O(N) time and O(1) additional space beyond the output list
Optimal Approach & Strategy
Perform one left‑to‑right pass, using direct index access to the two neighbours for each position, achieving O(N) time and O(N) auxiliary space for the result.
Brute Force Approach
For each index, scan the whole array to locate its left and right neighbours and compute the product, resulting in O(N^2) time.
Code Solutions
function peakSignals(signalStrengths) {
const n = signalStrengths.length;
const modified = new Array(n).fill(0);
if (n === 0) return modified; // empty input
if (n === 1) { // single element
modified[0] = 0;
return modified;
}
modified[0] = signalStrengths[1];
for (let i = 1; i < n - 1; ++i) {
modified[i] = signalStrengths[i - 1] * signalStrengths[i + 1];
}
modified[n - 1] = signalStrengths[n - 2];
return modified;
}
// ----- I/O handling (Node.js) -----
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++] || 0;
const signalStrengths = data.slice(pos, pos + n);
const result = peakSignals(signalStrengths);
console.log(result.join(' '));
#include <bits/stdc++.h>
using namespace std;
vector<int> peakSignals(const vector<int>& signalStrengths) {
int n = (int)signalStrengths.size();
vector<int> modified(n);
if (n == 0) return modified; // empty input
if (n == 1) { // only one element, no neighbours
modified[0] = 0;
return modified;
}
modified[0] = signalStrengths[1];
for (int i = 1; i < n - 1; ++i) {
modified[i] = signalStrengths[i - 1] * signalStrengths[i + 1];
}
modified[n - 1] = signalStrengths[n - 2];
return modified;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<int> signalStrengths(n);
for (int i = 0; i < n; ++i) cin >> signalStrengths[i];
vector<int> result = peakSignals(signalStrengths);
for (size_t i = 0; i < result.size(); ++i) {
if (i) cout << ' ';
cout << result[i];
}
cout << '\n';
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
// Returns the modified array according to the problem statement.
public static List<Integer> peakSignals(List<Integer> signalStrengths) {
int n = signalStrengths.size();
List<Integer> modified = new ArrayList<>(Collections.nCopies(n, 0));
if (n == 0) return modified; // empty input
if (n == 1) { // single element
modified.set(0, 0);
return modified;
}
modified.set(0, signalStrengths.get(1));
for (int i = 1; i < n - 1; ++i) {
int val = signalStrengths.get(i - 1) * signalStrengths.get(i + 1);
modified.set(i, val);
}
modified.set(n - 1, signalStrengths.get(n - 2));
return modified;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
List<Integer> signalStrengths = new ArrayList<>();
if (n > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
signalStrengths.add(Integer.parseInt(st.nextToken()));
}
}
List<Integer> result = peakSignals(signalStrengths);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(result.get(i));
}
System.out.println(sb.toString());
}
}
def peak_signals(signal_strengths):
"""Return the modified array as described in the problem statement."""
n = len(signal_strengths)
if n == 0:
return []
if n == 1:
return [0]
modified = [0] * n
modified[0] = signal_strengths[1]
for i in range(1, n - 1):
modified[i] = signal_strengths[i - 1] * signal_strengths[i + 1]
modified[-1] = signal_strengths[-2]
return modified
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
n = int(data[0])
signal_strengths = list(map(int, data[1:1 + n]))
result = peak_signals(signal_strengths)
print(' '.join(map(str, result)))
function peakSignals(signalStrengths) {
const n = signalStrengths.length;
const modified = new Array(n).fill(0);
if (n === 0) return modified; // empty input
if (n === 1) { // single element
modified[0] = 0;
return modified;
}
modified[0] = signalStrengths[1];
for (let i = 1; i < n - 1; ++i) {
modified[i] = signalStrengths[i - 1] * signalStrengths[i + 1];
}
modified[n - 1] = signalStrengths[n - 2];
return modified;
}
// ----- I/O handling (Node.js) -----
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++] || 0;
const signalStrengths = data.slice(pos, pos + n);
const result = peakSignals(signalStrengths);
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.