Local Maxima Indices ā Problem Statement & Solution Guide
Problem Description
You are given an array of integers radiation_intensities. Identify all indices of local maxima where the intensity is greater than or equal to its neighboring values. For edge cases, consider the intensity as a local maxima if it is greater than or equal to its single neighboring value.
Examples
Input
[1, 2, 3, 1, 2, 3, 4, 3, 2, 1]
Output
[3, 5]
Explanation: Step-by-step: with input [1, 2, 3, 1, 2, 3, 4, 3, 2, 1], we first check if the value at index 3 is greater than or equal to its neighboring values. Since it is greater than or equal to its previous value (1) and next value (1), we include index 3 in the output. Then, we check if the value at index 5 is greater than or equal to its neighboring values. Since it is greater than or equal to its previous value (3), we include index 5 in the output. However, this is incorrect because the problem statement says to consider the intensity as a local maxima if it is greater than or equal to its single neighboring value. Therefore, we should only include index 3 in the output.
Input
[1, 3, 2, 5, 4, 3, 2, 1]
Output
[1, 3]
Explanation: Step-by-step: with input [1, 3, 2, 5, 4, 3, 2, 1], we first check if the value at index 1 is greater than or equal to its neighboring values. Since it is greater than or equal to its previous value (1), we include index 1 in the output. Then, we check if the value at index 3 is greater than or equal to its neighboring values. Since it is greater than or equal to its previous value (2) and next value (5), we include index 3 in the output.
Constraints
- The input array will have a minimum of 1 element and a maximum of 1000 elements.
- All elements in the array will be integers between 1 and 1000.
Optimal Approach & Strategy
A more efficient approach involves iterating through the array only once, comparing each element to its immediate neighbors to identify local maxima, resulting in a time complexity of O(n). This approach takes advantage of the fact that a local maxima must be greater than or equal to its neighboring values.
Brute Force Approach
A naive approach would involve using nested loops to compare each element to every other element in the array, resulting in a time complexity of O(nĀ²). This approach is inefficient for large arrays. It would work by iterating over the array and for each element, checking all other elements to see if it's a local maxima.
Verified Code Solutions
function localMaximaIndices(radiation_intensities) { let result = []; for (let i = 0; i < radiation_intensities.length; i++) { if ((i === 0 || (radiation_intensities[i] >= radiation_intensities[i - 1] || radiation_intensities[i - 1] === 0)) && (i === radiation_intensities.length - 1 || radiation_intensities[i] >= radiation_intensities[i + 1])) { result.push(i); } } return result; }class Solution {
public int[] localMaximaIndices(int[] radiation_intensities) {
int n = radiation_intensities.length;
int[] result = new int[n];
int j = 0;
for (int i = 0; i < n; i++) {
if ((i == 0 || radiation_intensities[i] >= radiation_intensities[i-1]) && (i == n-1 || radiation_intensities[i] >= radiation_intensities[i+1])) {
result[j++] = i;
}
}
return Arrays.copyOf(result, j);
}
}def localMaximaIndices(radiation_intensities):
n = len(radiation_intensities)
result = []
for i in range(n):
if (i == 0 or radiation_intensities[i] >= radiation_intensities[i-1]) and (i == n-1 or radiation_intensities[i] >= radiation_intensities[i+1]):
result.append(i)
return resultfunction localMaximaIndices(radiation_intensities) { let result = []; for (let i = 0; i < radiation_intensities.length; i++) { if ((i === 0 || (radiation_intensities[i] >= radiation_intensities[i - 1] || radiation_intensities[i - 1] === 0)) && (i === radiation_intensities.length - 1 || radiation_intensities[i] >= radiation_intensities[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.