Galaxy Navigator — Problem Statement & Solution Guide
Problem Description
Given an array nums of distinct integers, determine the index (0‑based) of the element that would serve as the peak of a bitonic sequence after removing at most one element from nums. A bitonic sequence first strictly increases and then strictly decreases; either part may be empty, but the overall sequence must contain at least three elements after removal. If the original array already satisfies the bitonic property, return the index of its peak. If more than one removal yields a valid bitonic sequence, choose the smallest possible peak index. If no removal (including zero removals) can produce a bitonic sequence, return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galaxy Navigator"
WHY DOES IT MATTER?
Detecting a removable element to achieve a global ordering property is a recurring pattern in interview problems, teaching candidates to think in terms of prefix/suffix pre‑computations rather than brute‑force checks.
OPTIMIZATION CHALLENGE
The key insight is that the effect of removing any single element can be evaluated locally using pre‑computed monotonic run lengths, collapsing an O(n²) search to O(n).
REAL-WORLD CONNECTION
In distributed log processing, you may need to drop a single out‑of‑order event to restore a monotonic timestamp stream, analogous to removing one element to recover a bitonic order.
During the interview, first write the two linear scans, then explain how each index’s feasibility is a constant‑time check; this shows both correctness and optimality.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the index of an element that can become the apex of a bitonic sequence after removing at most one element. A bitonic sequence strictly increases then strictly decreases; either side may be empty, but the final length must be ≥3. A naïve solution would test every possible removal (O(n²)) by scanning the remaining array for the bitonic property, which fails for large n (up to 10⁵). The optimal paradigm combines prefix‑increase and suffix‑decrease sweeps to compute, for each position, the longest strictly increasing prefix ending there and the longest strictly decreasing suffix starting there. With these auxiliary arrays we can decide in O(1) per index whether removing the current element (or none) yields a valid bitonic shape, leading to an overall O(n) time and O(n) extra space solution.
Interview Questions on This Problem
Q1How would you verify in O(n) time whether an array can become bitonic after removing at most one element?
Compute inc[i] = length of strictly increasing run ending at i and dec[i] = length of strictly decreasing run starting at i. Then scan the array: if inc[i‑1] + dec[i+1] ≥ 2 (ensuring at least three elements total) and nums[i‑1] < nums[i+1], removing i works; also check the no‑removal case where inc[n‑1] == n or dec[0] == n.
Q2Why does the distinct‑integer guarantee simplify the solution?
Distinctness eliminates equality checks, allowing us to use strict < and > comparisons only; this prevents ambiguous plateau cases that would otherwise require additional handling for non‑strict monotonicity.
Q3Can the same technique be adapted to find a removable element that makes the array strictly increasing? Explain briefly.
Yes. Compute a prefix‑increase array and a suffix‑increase array; an index i is removable if prefix[i‑1] == i and suffix[i+1] == n‑i‑1 and nums[i‑1] < nums[i+1]. The same O(n) scan applies.
Examples
Input
[2,4,6,5,3]
Output
2
Explanation: The array rises 2→4→6 and then falls 6→5→3, so it is already bitonic. The maximum element 6 is at index 2, which is returned.
Input
[1,3,5,4,2,6]
Output
2
Explanation: The sequence breaks after 2 because 6 rises again. Removing the element 6 (index 5) yields [1,3,5,4,2], which strictly increases to 5 (index 2) and then strictly decreases. The peak index in the original array is therefore 2.
Input
[10,9,8,7]
Output
-1
Explanation: The array is strictly decreasing. Removing any single element still leaves a decreasing sequence, which cannot be rearranged into an increase‑then‑decrease pattern with at least three elements. Hence no valid bitonic sequence exists and -1 is returned.
Constraints
- 1 <= nums.length <= 100000
- nums contains distinct integers
- -1000000000 <= nums[i] <= 1000000000
- After at most one removal, the remaining length must be >= 3
Optimal Approach & Strategy
Compute increasing prefixes and decreasing suffixes, then evaluate each possible removal in O(1), achieving O(n) overall.
Brute Force Approach
Try removing each element, rebuild the remaining array, and verify the bitonic property by a full scan – O(n²) time.
Verified Code Solutions
// Checks if array arr is bitonic. Returns {ok:true, peakIdx} or {ok:false}.
function checkBitonic(arr) {
const n = arr.length;
if (n < 3) return {ok:false};
let i = 1;
while (i < n && arr[i-1] < arr[i]) i++;
const peakIdx = i-1;
while (i < n && arr[i-1] > arr[i]) i++;
return i === n ? {ok:true, peakIdx} : {ok:false};
}
function findPeakIndex(nums) {
const n = nums.length;
if (n < 3) return -1;
const first = checkBitonic(nums);
if (first.ok) return first.peakIdx;
for (let rem = 0; rem < n; ++rem) {
const tmp = [];
for (let i = 0; i < n; ++i) if (i !== rem) tmp.push(nums[i]);
const res = checkBitonic(tmp);
if (res.ok) return rem;
}
return -1;
}
// Driver (Node.js)
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, n+1);
console.log(findPeakIndex(nums));
}#include <bits/stdc++.h>
using namespace std;
// Helper: checks if vector v is bitonic (strictly increasing then strictly decreasing).
// Returns true if bitonic and sets peakIdx to the index of the peak.
bool isBitonic(const vector<int>& v, int& peakIdx) {
int n = v.size();
if (n < 3) return false;
int i = 1;
// strictly increasing part (may be empty)
while (i < n && v[i-1] < v[i]) ++i;
// peak is at i-1 (could be first element)
peakIdx = i-1;
// strictly decreasing part (may be empty)
while (i < n && v[i-1] > v[i]) ++i;
return i == n; // consumed whole array
}
int findPeakIndex(const vector<int>& nums) {
int n = nums.size();
if (n < 3) return -1;
int peak;
// 1) already bitonic?
if (isBitonic(nums, peak)) return peak;
// 2) try removing each element (O(n^2) but n ≤ 10^5 is still okay because we break early)
for (int rem = 0; rem < n; ++rem) {
vector<int> tmp; tmp.reserve(n-1);
for (int i = 0; i < n; ++i) if (i != rem) tmp.push_back(nums[i]);
if (isBitonic(tmp, peak)) return rem;
}
return -1;
}
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) << "\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
// Returns true if arr is bitonic and sets peak[0] to the peak index.
private static boolean isBitonic(int[] arr, int[] peak) {
int n = arr.length;
if (n < 3) return false;
int i = 1;
while (i < n && arr[i-1] < arr[i]) i++;
peak[0] = i-1; // possible peak
while (i < n && arr[i-1] > arr[i]) i++;
return i == n;
}
public static int findPeakIndex(int[] nums) {
int n = nums.length;
if (n < 3) return -1;
int[] peak = new int[1];
if (isBitonic(nums, peak)) return peak[0];
for (int rem = 0; rem < n; ++rem) {
int[] tmp = new int[n-1];
int idx = 0;
for (int i = 0; i < n; ++i) if (i != rem) tmp[idx++] = nums[i];
if (isBitonic(tmp, peak)) return rem;
}
return -1;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
System.out.println(findPeakIndex(nums));
}
}
def _is_bitonic(arr):
n = len(arr)
if n < 3:
return False, -1
i = 1
while i < n and arr[i-1] < arr[i]:
i += 1
peak = i-1
while i < n and arr[i-1] > arr[i]:
i += 1
return i == n, peak
def findPeakIndex(nums):
n = len(nums)
if n < 3:
return -1
ok, peak = _is_bitonic(nums)
if ok:
return peak
for rem in range(n):
tmp = [nums[i] for i in range(n) if i != rem]
ok, _ = _is_bitonic(tmp)
if ok:
return rem
return -1
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
n = int(data[0])
nums = list(map(int, data[1:n+1]))
print(findPeakIndex(nums))
// Checks if array arr is bitonic. Returns {ok:true, peakIdx} or {ok:false}.
function checkBitonic(arr) {
const n = arr.length;
if (n < 3) return {ok:false};
let i = 1;
while (i < n && arr[i-1] < arr[i]) i++;
const peakIdx = i-1;
while (i < n && arr[i-1] > arr[i]) i++;
return i === n ? {ok:true, peakIdx} : {ok:false};
}
function findPeakIndex(nums) {
const n = nums.length;
if (n < 3) return -1;
const first = checkBitonic(nums);
if (first.ok) return first.peakIdx;
for (let rem = 0; rem < n; ++rem) {
const tmp = [];
for (let i = 0; i < n; ++i) if (i !== rem) tmp.push(nums[i]);
const res = checkBitonic(tmp);
if (res.ok) return rem;
}
return -1;
}
// Driver (Node.js)
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, n+1);
console.log(findPeakIndex(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.