Astronaut's Oxygen Level Detector — Problem Statement & Solution Guide
Problem Description
Given an integer array nums that records oxygen levels in chronological order, identify an index i such that nums[i] is not smaller than its immediate neighbours. For interior positions (0<i<nums.length‑1) the condition is nums[i]≥nums[i‑1] and nums[i]≥nums[i+1]; for the first element only the right neighbour is considered and for the last element only the left neighbour. If several indices satisfy the condition, return any index whose value equals the maximum possible oxygen level among all qualifying positions. If the array is empty or no index meets the criteria, return -1. The algorithm must run in O(log n) time and use O(1) extra space, which can be achieved with a modified binary search that repeatedly discards the half that cannot contain a local maximum.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Astronaut's Oxygen Level Detector"
WHY DOES IT MATTER?
Peak detection appears in signal processing, load‑balancing, and resource allocation; mastering the binary‑search‑based pattern teaches you to exploit local monotonicity for sub‑linear solutions.
OPTIMIZATION CHALLENGE
The key insight is that a strictly increasing slope guarantees a peak on the far side, allowing you to discard half the array each step, turning an O(n) scan into O(log n).
REAL-WORLD CONNECTION
Think of a mountain range where you can only see the immediate left and right peaks; by walking towards the higher neighbour you are guaranteed to reach a summit without traversing the whole range—mirroring the algorithm’s directional narrowing.
During an interview, write the binary‑search loop iteratively, keep the neighbour checks inside the loop, and explicitly handle edge indices to avoid off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The task is a classic peak‑finding problem where we need an index i such that nums[i] is not smaller than its neighbours. A naïve scan checks every element and its neighbours, yielding O(n) time, which is acceptable for small inputs but becomes a bottleneck when n reaches 10⁷ or when the function is called repeatedly inside larger pipelines. The optimal solution leverages the monotonic property of the array: if nums[mid] < nums[mid+1], a peak must exist on the right half, otherwise it lies on the left. This binary‑search‑style divide‑and‑conquer reduces the search space by half each iteration, achieving O(log n) time while using O(1) extra space. The paradigm exemplifies how a simple observation about local ordering can transform a linear scan into a logarithmic‑time algorithm.
Interview Questions on This Problem
Q1How would you modify the peak‑finding algorithm to return any peak in a circular array where the first and last elements are neighbours?
Treat the array as circular by virtually extending the index range; during binary search compare nums[mid] with both neighbours using modulo arithmetic. The same monotonic reasoning holds, so you still achieve O(log n) time.
Q2At a fintech firm you need to guarantee a peak‑finding service runs under 1 ms for streams of 1 million price ticks. Which implementation details matter most?
Use an iterative binary search to avoid recursion overhead, access the underlying primitive array directly, and ensure branch prediction friendliness by minimizing conditional jumps; also pre‑allocate any needed variables to avoid GC pauses.
Q3A startup asks you to find a peak in a read‑only distributed list where each node holds a chunk of the array. How can you adapt the algorithm?
Perform a distributed binary search: query the middle node for its boundary values, decide which half contains a peak, and recursively request the next chunk. Communication cost becomes O(log k) where k is the number of nodes, preserving logarithmic rounds.
Examples
Input
[78,85,85,80,70]
Output
1
Explanation: Indices 1 and 2 both have value 85 and each is ≥ its neighbours. The highest oxygen level among qualifying indices is 85, so either index 1 or 2 is acceptable; the example returns 1.
Input
[]
Output
-1
Explanation: The array contains no measurements, therefore no index can satisfy the condition; the function returns -1.
Input
[92]
Output
0
Explanation: With a single element, it is trivially ≥ its (non‑existent) neighbours, so index 0 is returned.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- Expected time complexity: O(log n)
- Expected auxiliary space: O(1)
Optimal Approach & Strategy
Use an iterative binary search: at each step compare nums[mid] with nums[mid+1]; if nums[mid] < nums[mid+1] move right, else move left, until low equals high, which is a peak. This runs in O(log n) time.
Brute Force Approach
Loop through the array and for each index compare it with its neighbours; return the first index that satisfies the peak condition. This is O(n) time.
Verified Code Solutions
function findPeak(nums) {
const n = nums.length;
if (n === 0) return -1;
for (let i = 0; i < n; ++i) {
const leftOk = (i === 0) || nums[i] >= nums[i - 1];
const rightOk = (i === n - 1) || nums[i] >= nums[i + 1];
if (leftOk && rightOk) return i;
}
return -1;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
const n = data[0];
const nums = data.slice(1,1+n);
console.log(findPeak(nums));
}#include <bits/stdc++.h>
using namespace std;
int findPeak(const vector<int>& nums) {
int n = nums.size();
if(n==0) return -1;
for(int i=0;i<n;++i){
bool leftOk = (i==0) || nums[i]>=nums[i-1];
bool rightOk = (i==n-1) || nums[i]>=nums[i+1];
if(leftOk && rightOk) return i;
}
return -1; // never reached for non‑empty array
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n; if(!(cin>>n)) return 0;vector<int> a(n);for(int i=0;i<n;++i)cin>>a[i];cout<<findPeak(a);return 0;}import java.io.*;
import java.util.*;
public class Main {
public static int findPeak(int[] nums) {
int n = nums.length;
if (n == 0) return -1;
for (int i = 0; i < n; ++i) {
boolean leftOk = (i == 0) || nums[i] >= nums[i-1];
boolean rightOk = (i == n-1) || nums[i] >= nums[i+1];
if (leftOk && rightOk) return i;
}
return -1; // unreachable for non‑empty array
}
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;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
int idx = 0;
while (idx < n) {
if (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
continue;
}
nums[idx++] = Integer.parseInt(st.nextToken());
}
System.out.println(findPeak(nums));
}
}def find_peak(nums):
n = len(nums)
if n == 0:
return -1
for i in range(n):
left_ok = (i == 0) or nums[i] >= nums[i-1]
right_ok = (i == n-1) or nums[i] >= nums[i+1]
if left_ok and right_ok:
return i
return -1
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
n = data[0]
nums = data[1:1+n]
print(find_peak(nums))function findPeak(nums) {
const n = nums.length;
if (n === 0) return -1;
for (let i = 0; i < n; ++i) {
const leftOk = (i === 0) || nums[i] >= nums[i - 1];
const rightOk = (i === n - 1) || nums[i] >= nums[i + 1];
if (leftOk && rightOk) return i;
}
return -1;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
const n = data[0];
const nums = data.slice(1,1+n);
console.log(findPeak(nums));
}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.