Find All Strict Local Maxima in an Integer Array
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given an integer array, return the indices of all of its local maxima. The report says only that the task was to find a local maximum in an array; this version asks for every local maximum so that the answer is unique.
### Function Signature
```python
def local_maxima(nums: list[int]) -> list[int]:
```
### Rules
- Index `i` is a local maximum when `nums[i]` is strictly greater than each of its neighbours that exist: `nums[i - 1]` when `i > 0`, and `nums[i + 1]` when `i < len(nums) - 1`.
- The first and last elements have one neighbour each. In a one-element array, the only element is a local maximum.
- Equal neighbours do not count: in `[4, 4]`, neither element is a local maximum.
- Return the indices in increasing order, or an empty list if there are none.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
### Examples
**Example 1**
```text
Input: nums = [1, 3, 2, 4, 1]
Output: [1, 3]
```
`3` is greater than `1` and `2`, and `4` is greater than `2` and `1`.
**Example 2**
```text
Input: nums = [5, 5, 4, 6]
Output: [3]
```
The two `5`s are equal neighbours, so neither is a local maximum. The last element, `6`, has one neighbour, `4`, and is greater than it.
**Example 3**
```text
Input: nums = [7]
Output: [0]
```
A single element has no neighbours, so it is a local maximum.
Overview: A coding question asking for the indices of every strict local maximum in an integer array, where boundary elements compare only with their single neighbour and equal neighbours never count. It tests careful handling of array boundaries, plateaus of equal values and single-element input.
Read the full Pinterest Machine Learning Engineer interview experience this question came from
Given an integer array `nums`, return the indices of all of its local maxima.
Index `i` is a **local maximum** when `nums[i]` is strictly greater than each of its neighbours that exist: `nums[i - 1]` when `i > 0`, and `nums[i + 1]` when `i < len(nums) - 1`.
- The first and last elements have one neighbour each. In a one-element array, the only element is a local maximum.
- Equal neighbours do not count: in `[4, 4]`, neither element is a local maximum.
- Return the indices in increasing order, or an empty list if there are none.
Implement `local_maxima(nums)`, which returns that list of indices.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
No input value or returned index exceeds 2^31 - 1, so 32-bit integers (`int` in Java and C++) hold every value.
### Examples
**Example 1**
```text
Input: nums = [1, 3, 2, 4, 1]
Output: [1, 3]
```
`3` is greater than `1` and `2`, and `4` is greater than `2` and `1`.
**Example 2**
```text
Input: nums = [5, 5, 4, 6]
Output: [3]
```
The two `5`s are equal neighbours, so neither is a local maximum. The last element, `6`, has one neighbour, `4`, and is greater than it.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
Examples
Input: ([7],)
Expected Output: [0]
Explanation: Source example 3: a one-element array has no neighbours, so index 0 is a local maximum.
Input: ([-1000000000],)
Expected Output: [0]
Explanation: Singleton at the lower value bound -10^9 is still a local maximum; a scan over interior indices only would return [].
Hints
- Whether an index qualifies depends only on its own value and the values immediately beside it.
- The first and last positions have only one neighbour, and a one-element array has none; make sure every position is considered.
- The comparison is strict: a neighbour with an equal value disqualifies an index.