346. Find It in the Hidden Mountain
A hiking club has recorded the height of a ridge at equally spaced points, and the data is stored in a special read-only object called mountain. The heights rise strictly to one highest point and then fall strictly, so the shape is a single mountain: at least three points, and the highest one is never the first or the last.
You cannot read the data as an array. You may only call mountain.length() to get the number of points and mountain.get(i) to read the height at index i. Return the smallest index whose height equals target, or -1 if no point has that height. You may call get at most 100 times.
Example 1
- Input:
- target = 3, mountain = [1,3,5,4,2]
- Output:
- 1
- Explanation:
The height 3 appears at index 1 on the way up, and nowhere else, so the answer is 1.
Example 2
- Input:
- target = 6, mountain = [2,4,6,8,10,12,9,7,6,3,1]
- Output:
- 2
- Explanation:
The height 6 is at index 2 on the way up and again at index 8 on the way down; the smaller index is 2.
Constraints
3 ≤ mountain.length() ≤ 104
0 ≤ mountain.get(i), target ≤ 109
The values strictly increase up to the peak and then strictly decrease.
At most 100 calls to get.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
- Calls
- You may call
MountainArray.get(index), MountainArray.length()at most 100 times per case. It is provided; you do not write it.
Expected complexity
- Time
- O(log n)
- Space
- O(1)