Peak Energy Indices ā Problem Statement & Solution Guide
Problem Description
Given an array of integers energyReadings, find all indices i where the value at index i is greater than or equal to its neighboring values. If the value is at the edge of the array, it only needs to be greater than or equal to its one neighboring value.
Examples
Input
[1, 2, 3, 2, 1]
Output
[0, 2, 4]
Explanation: Step-by-step: with input [1, 2, 3, 2, 1], we compare each element with its neighbors. At index 0, 1 is less than 2, so it's not included. At index 1, 2 is less than 3, so it's not included. At index 2, 3 is greater than both its neighbors (2 and 2), so it's included. At index 3, 2 is less than 3, so it's not included. At index 4, 1 is greater than its only neighbor (2), so it's included. At index 0, 1 is also greater than its only neighbor, so it's included. Therefore, the output is [0, 2, 4].
Input
[1, 2, 1, 2, 3, 2, 1]
Output
[0, 3, 5, 6]
Explanation: Step-by-step: with input [1, 2, 1, 2, 3, 2, 1], we compare each element with its neighbors. At index 0, 1 is greater than its only neighbor (2), so it's included. At index 1, 2 is not greater than its neighbors, so it's not included. At index 2, 1 is not greater than its neighbors, so it's not included. At index 3, 2 is less than 3, so it's not included. At index 4, 3 is greater than both its neighbors (2 and 2), so it's included. At index 5, 2 is greater than its only neighbor (1), so it's included. At index 6, 1 is greater than its only neighbor (2), so it's included. Therefore, the output is [0, 3, 5, 6].
Constraints
- 1 <= length of array <= 10^5
- -10^5 <= each energy reading <= 10^5
Optimal Approach & Strategy
The optimal approach involves iterating over the array once and comparing each element with its neighbors, resulting in a solution with O(n) time complexity. This approach takes advantage of the fact that each element only needs to be compared with its immediate neighbors.
Brute Force Approach
One possible approach is to compare each element with its neighbors using nested loops, resulting in a brute-force solution with O(nĀ²) time complexity. This approach is not efficient for large arrays. The brute-force approach involves checking every element's neighbors, which leads to redundant comparisons.
Verified Code Solutions
function peakEnergyIndices(energyReadings) { let result = []; for (let i = 0; i < energyReadings.length; i++) { if (i === 0) { if (energyReadings[i] >= (energyReadings[i + 1] || -Infinity)) { result.push(i); } } else if (i === energyReadings.length - 1) { if (energyReadings[i] >= (energyReadings[i - 1] || -Infinity)) { result.push(i); } } else { if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) { result.push(i); } } } return result; }class Solution {
public int[] peakEnergyIndices(int[] energyReadings) {
int n = energyReadings.length;
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((i == 0 && energyReadings[i] >= energyReadings[i + 1]) ||
(i == n - 1 && energyReadings[i] >= energyReadings[i - 1]) ||
(i > 0 && i < n - 1 && energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1])) {
result.add(i);
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
res[i] = result.get(i);
}
return res;
}
}def peakEnergyIndices(energyReadings):
n = len(energyReadings)
result = []
for i in range(n):
if (i == 0 and energyReadings[i] >= energyReadings[i + 1]) or
(i == n - 1 and energyReadings[i] >= energyReadings[i - 1]) or
(i > 0 and i < n - 1 and energyReadings[i] >= energyReadings[i - 1] and energyReadings[i] >= energyReadings[i + 1]):
result.append(i)
return resultfunction peakEnergyIndices(energyReadings) { let result = []; for (let i = 0; i < energyReadings.length; i++) { if (i === 0) { if (energyReadings[i] >= (energyReadings[i + 1] || -Infinity)) { result.push(i); } } else if (i === energyReadings.length - 1) { if (energyReadings[i] >= (energyReadings[i - 1] || -Infinity)) { result.push(i); } } else { if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) { result.push(i); } } } return result; }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.