mediumArraysPattern: binary search
Peak Asteroid Index Solution
Problem Statement
You are given an array of integers `asteroidSizes` representing the sizes of asteroids in a belt. The sizes follow a pattern where they first increase and then decrease, but at most one asteroid might have been displaced, altering the pattern. Find the index of the largest asteroid if the pattern can be restored by removing at most one asteroid.
Examples
Example 1:
Input:{"asteroidSizes":[1,2,3,4,5,4,3,2,1]}
Output:4
Example 2:
Input:{"asteroidSizes":[1,2,3,5,4,3,2,1]}
Output:3
Constraints
- 1 <= array length <= 10^5
- Each element in the array is a positive integer.
Time: O(n) Space: O(1)
The optimal solution utilizes a modified binary search algorithm to find the peak element in the array, which represents the largest asteroid, and handles edge cases where the peak might be at the start or end of the array. It iterates through the array to identify the transition from increasing to decreasing size, indicating the position of the largest asteroid.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.