Find First Local Minimum
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums`, find the index of the first local minimum.
A local minimum is an element that is smaller than its immediate neighbors:
- For an interior index `i`, `nums[i]` is a local minimum if `nums[i] < nums[i - 1]` and `nums[i] < nums[i + 1]`.
- For index `0`, it is a local minimum if the array has length `1`, or if `nums[0] < nums[1]`.
- For index `n - 1`, it is a local minimum if `nums[n - 1] < nums[n - 2]`.
Return the smallest index that satisfies the local-minimum condition. If no local minimum exists, return `-1`.
Example:
```text
Input: nums = [5, 3, 4, 2, 6]
Output: 1
Explanation: nums[1] = 3 and nums[3] = 2 are both local minima, but index 1 is the first one.
```
Quick Answer: This question evaluates array-processing and algorithmic reasoning skills, specifically the ability to identify local minima and handle index-based and boundary-case conditions.
Given an integer array `nums`, return the index of the first local minimum. A local minimum is an element that is strictly smaller than its immediate neighbors. For an interior index `i`, `nums[i]` is a local minimum if `nums[i] < nums[i - 1]` and `nums[i] < nums[i + 1]`. For index `0`, it is a local minimum if the array has length `1`, or if `nums[0] < nums[1]`. For index `n - 1`, it is a local minimum if `nums[n - 1] < nums[n - 2]`. Return the smallest index that satisfies this condition. If no local minimum exists, return `-1`. If the array is empty, return `-1`.
Constraints
- 0 <= len(nums) <= 100000
- -1000000000 <= nums[i] <= 1000000000
Examples
Input: [5, 3, 4, 2, 6]
Expected Output: 1
Explanation: Index 1 is a local minimum because 3 < 5 and 3 < 4. Although index 3 is also a local minimum, the first one is at index 1.
Input: [2, 3, 4]
Expected Output: 0
Explanation: Index 0 is a local minimum because 2 < 3.
Hints
- You only need to compare each element with its immediate neighbors, not the whole array.
- Handle the boundary indices `0` and `n - 1` separately, then scan from left to right to find the first valid position.