Peak Asteroid Index — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Peak Asteroid Index problem optimally.
O(log n)O(1)Problem Description
You are provided with an integer array asteroidSizes representing the mass distribution of a binary star system's debris field. The array is structured as a 'mountain' sequence: it begins with a strictly increasing segment, reaches a single global maximum, and concludes with a strictly decreasing segment. However, due to measurement noise, there may be at most one adjacent pair of elements that violates the strict monotonicity rules (i.e., a local dip or flat spot) in either the ascending or descending phase. Your task is to identify the index of the unique maximum element in this array.
The solution must be efficient, leveraging the structural properties of the array to achieve a time complexity of O(log n) and a space complexity of O(1). You cannot simply scan the array linearly, as the input size can be very large. Instead, you must employ a binary search strategy that correctly handles the potential single anomaly in the sequence to pinpoint the peak.
Return the index of the maximum value. If the array contains only one element, return 0. The maximum value is guaranteed to be unique, even if the surrounding sequence has a minor irregularity.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Peak Asteroid Index"
WHY DOES IT MATTER?
Peak‑finding is a classic example of exploiting order to shrink search space dramatically, a skill that translates to many real‑world problems like load‑balancing, latency spikes, and financial time‑series analysis where you need the extremum quickly.
OPTIMIZATION CHALLENGE
The key insight is that a single comparison with the right neighbor tells you which side still respects the increasing‑then‑decreasing shape, allowing you to discard half the array each iteration despite a possible local disorder.
REAL-WORLD CONNECTION
Imagine a network of sensors reporting temperature that rises to a hotspot and then falls; locating the hotspot with minimal queries mirrors the binary‑search peak algorithm, saving bandwidth and power in IoT deployments.
During the interview, write the loop invariant first: low <= peak <= high and maintain it by moving low = mid+1 or high = mid based on the neighbor comparison—this keeps your code bug‑free.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The array described is a unimodal sequence with a single peak, possibly corrupted by one adjacent inversion. A naïve linear scan finds the maximum in O(n) time, which is unacceptable for very large n because interviewers expect logarithmic solutions that demonstrate divide‑and‑conquer mastery. The optimal paradigm is a modified binary search that leverages the monotonic property on either side of the peak: if the middle element is greater than its right neighbor, the peak lies at mid or to the left; otherwise it lies to the right. This decision rule works even when a single adjacent pair violates strict ordering, because the violation can be detected by comparing both neighbors and adjusting the search interval accordingly, guaranteeing O(log n) steps.
Interview Questions on This Problem
Q1How would you adapt the binary‑search peak‑finding algorithm if the array could contain up to two adjacent violations instead of one?
You would first locate any violation by scanning around the mid point; if a violation is found, treat the sub‑array on the side opposite the larger neighbor as still unimodal and continue binary search, otherwise fall back to the standard peak‑finding rule. In the worst case you may need an extra O(log n) pass to skip the second violation, preserving overall logarithmic complexity.
Q2Why is it safe to compare arr[mid] with arr[mid+1] without checking bounds in this problem?
The problem guarantees that the array length is at least 3 and the peak is not at the extreme ends, so mid will never be the last index during the binary‑search loop; the loop invariant maintains low < high, ensuring mid+1 is a valid index.
Q3Explain how the peak‑finding technique relates to finding the maximum in a rotated sorted array.
Both problems exploit a monotonic segment on each side of a pivot (peak or rotation point). By comparing the middle element with a neighbor, you can decide which half still preserves the ordering property and discard the other half, achieving O(log n) time for both scenarios.
Examples
Input
asteroidSizes = [1, 3, 5, 4, 2]
Output
2
Explanation: The array increases from 1 to 5, then decreases to 2. The maximum value is 5, located at index 2. The sequence is strictly increasing then strictly decreasing, with no anomalies. Binary search will converge on index 2 as the peak.
Input
asteroidSizes = [1, 2, 2, 4, 3]
Output
3
Explanation: The array has a flat spot at indices 1 and 2 (both value 2). The sequence is 1, 2, 2, 4, 3. The maximum is 4 at index 3. The anomaly is the equal pair (2,2). A standard binary search must handle the case where `asteroidSizes[mid] == asteroidSizes[mid+1]` or similar to avoid getting stuck, but since the peak is unique and higher, the search will still converge to index 3.
Input
asteroidSizes = [5, 4, 3, 2, 1]
Output
0
Explanation: The array is strictly decreasing. The maximum value is 5, located at index 0. This is an edge case where the peak is at the boundary. Binary search must handle the case where the left neighbor is always greater, indicating the peak is to the left.
Input
asteroidSizes = [1, 2, 3, 3, 4, 5, 4, 3]
Output
5
Explanation: The array increases to 5 at index 5, then decreases. There is a flat spot at indices 2 and 3 (both value 3). The maximum is 5 at index 5. The binary search will compare midpoints and adjust the search range based on the slope, eventually isolating index 5.
Constraints
- 1 <= asteroidSizes.length <= 10^5
- 1 <= asteroidSizes[i] <= 10^9
- The array is a mountain array with at most one adjacent pair that does not strictly increase or decrease.
- The maximum element is unique.
- The array is not empty.
Optimal Approach & Strategy
Use a modified binary search that compares the middle element with its right neighbor to decide which half contains the peak, halving the search space each iteration.
Brute Force Approach
Scan the entire array once, tracking the largest value and its index.
Code Solutions
function peakIndexInMountainArray(arr){
let l=0, r=arr.length-1;
while(l<r){
const mid=Math.floor((l+r)/2);
if(arr[mid] < arr[mid+1]) l=mid+1; else r=mid;
}
return l;
}
function main(){
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n=data[0];
const arr=data.slice(1,1+n);
console.log(peakIndexInMountainArray(arr));
}
main();#include <bits/stdc++.h>
using namespace std;
int peakIndexInMountainArray(const vector<int>& arr){
int l=0, r=(int)arr.size()-1;
while(l<r){
int mid=l+(r-l)/2;
if(arr[mid] < arr[mid+1]) l=mid+1; else r=mid;
}
return l;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> arr(n);
for(int i=0;i<n;++i)cin>>arr[i];
cout<<peakIndexInMountainArray(arr);
return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int peakIndexInMountainArray(int[] arr){
int l=0, r=arr.length-1;
while(l<r){
int mid=l+(r-l)/2;
if(arr[mid] < arr[mid+1]) l=mid+1; else r=mid;
}
return l;
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line=br.readLine();
if(line==null||line.isEmpty()) return;
int n=Integer.parseInt(line.trim());
int[] arr=new int[n];
if(n>0){
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) arr[i]=Integer.parseInt(st.nextToken());
}
System.out.println(peakIndexInMountainArray(arr));
}
}
def peak_index_in_mountain_array(arr):
l, r = 0, len(arr) - 1
while l < r:
mid = (l + r) // 2
if arr[mid] < arr[mid + 1]:
l = mid + 1
else:
r = mid
return l
def main():
import sys
data=list(map(int,sys.stdin.read().strip().split()))
if not data:
return
n=data[0]
arr=data[1:1+n]
print(peak_index_in_mountain_array(arr))
if __name__=="__main__":
main()
function peakIndexInMountainArray(arr){
let l=0, r=arr.length-1;
while(l<r){
const mid=Math.floor((l+r)/2);
if(arr[mid] < arr[mid+1]) l=mid+1; else r=mid;
}
return l;
}
function main(){
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n=data[0];
const arr=data.slice(1,1+n);
console.log(peakIndexInMountainArray(arr));
}
main();
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.