Identify Local Maxima ā Problem Statement & Solution Guide
Problem Description
Given a list of distinct integer values in an array arr, find all elements that are greater than their immediate neighbors.
Examples
Input
[2, 3, 5, 7, 9, 10]
Output
[3, 5, 7, 9]
Explanation: Step-by-step: Given the array [2, 3, 5, 7, 9, 10], we iterate through the array. At index 1, we find 3 which is greater than its previous element 2. At index 2, we find 5 which is greater than its previous element 3. At index 3, we find 7 which is greater than its previous element 5. At index 4, we find 9 which is greater than its previous element 7. However, at index 5, we find 10 which is not greater than its previous element 9. Therefore, the output is [3, 5, 7, 9].
Input
[10]
Output
[10]
Explanation: Step-by-step: Given the array [10], we iterate through the array. Since there is only one element, it is considered as a local maxima. Therefore, the output is [10].
Constraints
- The list of asteroid sizes will have at least 3 elements.
- All asteroid sizes will be distinct integers between 1 and 100.
Optimal Approach & Strategy
The optimal approach involves iterating over the list of asteroid sizes once, using a single loop to compare each asteroid with its neighbors, resulting in a time complexity of O(n).
Brute Force Approach
A naive approach would involve using nested loops to compare each asteroid with its neighbors, resulting in a time complexity of O(nĀ²). This approach is inefficient and should be avoided for large inputs.
Verified Code Solutions
function identifyLocalMaxima(arr) { let result = []; for (let i = 1; i < arr.length - 1; i++) { if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) { result.push(arr[i]); } } return result; }class Solution {
public int[] identifyLocalMaxima(int[] arr) {
int[] localMaxima = new int[arr.length];
int index = 0;
for (int i = 1; i < arr.length - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
localMaxima[index++] = arr[i];
}
}
return Arrays.copyOf(localMaxima, index);
}
}def identify_local_maxima(arr):
local_maxima = []
for i in range(1, len(arr) - 1):
if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
local_maxima.append(arr[i])
return local_maximafunction identifyLocalMaxima(arr) { let result = []; for (let i = 1; i < arr.length - 1; i++) { if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) { result.push(arr[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.