Galaxy Navigation Peak — Problem Statement & Solution Guide
Problem Description
Given an array nums of length n containing integer masses of celestial bodies, identify the smallest index i such that nums[i] equals the maximum value present in the entire array. Indices are zero‑based. If the array is empty, return -1. The solution should run in O(log n) time and O(1) extra space, employing a modified binary‑search technique that narrows the search interval based on comparisons with neighboring elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galaxy Navigation Peak"
WHY DOES IT MATTER?
Finding the first occurrence of an extreme value in logarithmic time is a recurring pattern in search‑heavy services like leaderboard ranking, price‑feed updates, and log‑analysis where latency matters.
OPTIMIZATION CHALLENGE
The key insight is that once you know the global maximum, any index to the left that does not equal it can be discarded, allowing the search interval to be cut in half each step, turning a linear scan into a binary search.
REAL-WORLD CONNECTION
Imagine a distributed sensor network where each node reports a temperature; you need the earliest node that recorded the day's peak temperature. Instead of polling every node, you query halves of the network recursively, narrowing down to the first peak sensor.
During an interview, first state the O(n) baseline, then immediately propose the “first‑true” binary search and walk through how you maintain low, high, and a candidate answer to guarantee the leftmost index.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The problem asks for the leftmost occurrence of the global maximum in a sorted‑by‑index array, which can be solved with a classic binary‑search variant. A naive linear scan would examine every element, yielding O(n) time; this becomes prohibitive when n reaches millions or when the function is called repeatedly in performance‑critical services. By exploiting the monotonic property that any element to the left of a maximum cannot be larger, we can repeatedly halve the search interval, guaranteeing logarithmic steps. The optimal paradigm is a “first‑true” binary search: we maintain a low‑high window, test the middle element against the current global maximum (pre‑computed or discovered on‑the‑fly), and shrink the window toward the earliest index that still satisfies the maximum condition, achieving O(log n) time with O(1) extra space.
Interview Questions on This Problem
Q1How would you modify the binary search if the array could contain multiple equal maximum values and you need the first occurrence?
Compute the maximum value (or keep it while scanning) then run a binary search that, when nums[mid]==max, moves the high pointer to mid‑1 while recording mid as a candidate; finally return the recorded index.
Q2Can you solve the problem in O(log n) without a separate pass to find the maximum value?
Yes. Perform a binary search that compares nums[mid] with nums[mid+1]; if nums[mid] < nums[mid+1] the maximum lies to the right, otherwise it lies at mid or left, and continue until low==high, which will be the leftmost maximum.
Q3What edge cases must you guard against when implementing the binary‑search solution for an empty array or a single‑element array?
Return -1 immediately for an empty array; for a single element, the algorithm should correctly identify index 0 as the answer without accessing out‑of‑bounds neighbors.
Examples
Input
[4,2,9,9,3]
Output
2
Explanation: The maximum mass is 9. It appears at positions 2 and 3; the first occurrence is at index 2, which is returned.
Input
[-5,-1,-3]
Output
1
Explanation: The largest value in the list is -1, located at index 1. No earlier element equals -1, so the answer is 1.
Input
[7]
Output
0
Explanation: A single‑element array has its sole element as the maximum. Its index 0 is the required result.
Constraints
- 1<=nums.length<=200000
- -1000000000<=nums[i]<=1000000000
- Array may contain duplicate values
- All operations must use O(1) additional memory
Optimal Approach & Strategy
First find the maximum (or use a two‑pointer binary search that compares mid with its neighbor) and then binary‑search for the leftmost occurrence, shrinking the interval by half each iteration.
Brute Force Approach
Linearly scan the array, track the maximum value and its first index, and return that index after the pass.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function findPeakIndex(arr){
if(arr.length===0) return -1;
let maxVal = arr[0];
for(const v of arr) if(v>maxVal) maxVal=v;
let lo=0, hi=arr.length-1, ans=-1;
while(lo<=hi){
const mid = lo + ((hi-lo)>>1);
if(arr[mid]===maxVal){
ans=mid;
hi=mid-1;
}else if(arr[mid]<maxVal){
lo=mid+1;
}else{
hi=mid-1;
}
}
return ans;
}
const result = findPeakIndex(nums);
process.stdout.write(String(result));#include <bits/stdc++.h>
using namespace std;
int findPeakIndex(const vector<int>& nums){
if(nums.empty()) return -1;
// First pass to find the maximum value (O(n))
int maxVal = nums[0];
for(int v: nums) if(v>maxVal) maxVal=v;
// Binary search for the first occurrence of maxVal
int lo=0, hi=nums.size()-1, ans=-1;
while(lo<=hi){
int mid = lo + (hi-lo)/2;
if(nums[mid]==maxVal){
ans=mid; // possible answer, continue left to find earlier occurrence
hi=mid-1;
}else if(nums[mid]<maxVal){
lo=mid+1;
}else{ // nums[mid] > maxVal cannot happen because maxVal is maximum
hi=mid-1;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
cout<<findPeakIndex(nums);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static int findPeakIndex(int[] nums){
if(nums.length==0) return -1;
int maxVal = nums[0];
for(int v: nums) if(v>maxVal) maxVal=v;
int lo=0, hi=nums.length-1, ans=-1;
while(lo<=hi){
int mid = lo + (hi-lo)/2;
if(nums[mid]==maxVal){
ans=mid;
hi=mid-1;
}else if(nums[mid]<maxVal){
lo=mid+1;
}else{
hi=mid-1;
}
}
return ans;
}
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());
nums[idx++] = Integer.parseInt(st.nextToken());
}
System.out.print(findPeakIndex(nums));
}
}import sys
def find_peak_index(nums):
if not nums:
return -1
max_val = max(nums)
lo, hi = 0, len(nums)-1
ans = -1
while lo <= hi:
mid = (lo+hi)//2
if nums[mid] == max_val:
ans = mid
hi = mid-1
elif nums[mid] < max_val:
lo = mid+1
else:
hi = mid-1
return ans
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(find_peak_index(nums))
if __name__ == "__main__":
main()const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos=0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function findPeakIndex(arr){
if(arr.length===0) return -1;
let maxVal = arr[0];
for(const v of arr) if(v>maxVal) maxVal=v;
let lo=0, hi=arr.length-1, ans=-1;
while(lo<=hi){
const mid = lo + ((hi-lo)>>1);
if(arr[mid]===maxVal){
ans=mid;
hi=mid-1;
}else if(arr[mid]<maxVal){
lo=mid+1;
}else{
hi=mid-1;
}
}
return ans;
}
const result = findPeakIndex(nums);
process.stdout.write(String(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.