Peak Signals in Modified Array — Problem Statement & Solution Guide
Problem Description
Given an array of integers signalStrengths, modify the array by replacing each signal strength with the product of its neighboring signals. For edge signals, consider only the existing neighbor. Identify the indices of peak signals in the modified array, where a peak signal is one that is not weaker than its neighbors.
Examples
Input
[2, 3, 5]
Output
[2, 6, 6]
Explanation: Step 1: For the first element (2), its neighboring signals are 3 and 5. The product of these signals is 2 * 3 = 6. However, since the problem statement asks for the product of neighboring signals, we consider the existing neighbor for edge signals. So, the first element remains 2. Step 2: For the second element (3), its neighboring signals are 2 and 5. The product of these signals is 3 * 2 = 6. Step 3: For the third element (5), its neighboring signals are 3 and null (since it's the last element). The product of these signals is 5 * 3 = 15. However, since the problem statement asks for the product of neighboring signals, we consider the existing neighbor for edge signals. So, the third element remains 6 (which is the result of the second element). Therefore, the modified array is [2, 6, 6].
Input
[20, 2, 4, 3, 6]
Output
[20, 4, 10, 6, 6]
Explanation: Step 1: For the first element (20), its neighboring signals are null and 2. The product of these signals is 20 * 2 = 40. However, since the problem statement asks for the product of neighboring signals, we consider the existing neighbor for edge signals. So, the first element remains 20. Step 2: For the second element (2), its neighboring signals are 20 and 4. The product of these signals is 2 * 20 = 40. Step 3: For the third element (4), its neighboring signals are 2 and 3. The product of these signals is 4 * 2 = 8. Step 4: For the fourth element (3), its neighboring signals are 4 and 6. The product of these signals is 3 * 4 = 12. Step 5: For the fifth element (6), its neighboring signals are 3 and null (since it's the last element). The product of these signals is 6 * 3 = 18. However, since the problem statement asks for the product of neighboring signals, we consider the existing neighbor for edge signals. So, the fifth element remains 6. Therefore, the modified array is [20, 4, 10, 6, 6].
Constraints
- 1 <= array length <= 1000
- All elements in the array are positive integers
Optimal Approach & Strategy
Using a more efficient approach involves iterating over the array and modifying each element based on the product of its neighboring signals. This allows for a constant amount of work to be done for each element, resulting in a time complexity of O(n).
Brute Force Approach
The brute-force approach would consider every element in the array, comparing it to its neighbors to determine if it is a peak signal. However, this approach would lead to a time complexity of O(n^2) due to the nested loops required.
Verified Code Solutions
function peakSignals(signalStrengths) { let modified = []; for (let i = 0; i < signalStrengths.length; i++) { if (i === 0) { modified.push(signalStrengths[i] * (signalStrengths[i + 1] || Infinity)); } else if (i === signalStrengths.length - 1) { modified.push(signalStrengths[i] * (signalStrengths[i - 1] || Infinity)); } else { modified.push(signalStrengths[i - 1] * signalStrengths[i + 1]); } } let peaks = []; for (let i = 0; i < modified.length; i++) { if ((i === 0 || modified[i] >= modified[i - 1]) && (i === modified.length - 1 || modified[i] >= modified[i + 1])) { peaks.push(i); } } return peaks; }class Solution {
public int[] solution(int[] signalStrengths) {
if (signalStrengths.length == 1) {
return new int[] {signalStrengths[0]};
}
int[] modified = new int[signalStrengths.length];
modified[0] = signalStrengths[0] * signalStrengths[1];
for (int i = 1; i < signalStrengths.length - 1; i++) {
modified[i] = signalStrengths[i] * signalStrengths[i - 1] * signalStrengths[i + 1];
}
modified[signalStrengths.length - 1] = signalStrengths[signalStrengths.length - 1] * signalStrengths[signalStrengths.length - 2];
int[] peakSignals = new int[signalStrengths.length];
int j = 0;
for (int i = 0; i < modified.length; i++) {
if ((i == 0 || modified[i] >= modified[i - 1]) && (i == modified.length - 1 || modified[i] >= modified[i + 1])) {
peakSignals[j++] = i;
}
}
return Arrays.copyOf(peakSignals, j);
}
}def solution(signalStrengths):
if len(signalStrengths) == 1:
return [signalStrengths[0]]
modified = [signalStrengths[0] * signalStrengths[1]]
for i in range(1, len(signalStrengths) - 1):
modified.append(signalStrengths[i] * signalStrengths[i - 1] * signalStrengths[i + 1])
modified.append(signalStrengths[-1] * signalStrengths[-2])
peakSignals = []
for i in range(len(modified)):
if (i == 0 or modified[i] >= modified[i - 1]) and (i == len(modified) - 1 or modified[i] >= modified[i + 1]):
peakSignals.append(i)
return peakSignalsfunction peakSignals(signalStrengths) { let modified = []; for (let i = 0; i < signalStrengths.length; i++) { if (i === 0) { modified.push(signalStrengths[i] * (signalStrengths[i + 1] || Infinity)); } else if (i === signalStrengths.length - 1) { modified.push(signalStrengths[i] * (signalStrengths[i - 1] || Infinity)); } else { modified.push(signalStrengths[i - 1] * signalStrengths[i + 1]); } } let peaks = []; for (let i = 0; i < modified.length; i++) { if ((i === 0 || modified[i] >= modified[i - 1]) && (i === modified.length - 1 || modified[i] >= modified[i + 1])) { peaks.push(i); } } return peaks; }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.