Return the first local minimum in a list
An element is a local minimum if it is strictly smaller than both of its neighbours. Scan the list left to right and return the first such value. If there is no local minimum, return None. Treat only interior positions as candidates (the first and last elements have only one neighbour, so they do not qualify).
Example: [1, 2, 1, 2, 3, 4, 5, 6] → 1 (the value at index 2).
def first_local_min(x: list[int]) -> int | None:
# your code hereWrite the implementation.
Scan interior indices 1..len-2 and return x[i] at the first i where x[i] < x[i-1] and x[i] < x[i+1]; return None if none match. The decision is endpoint handling: with only interior candidates, lists shorter than 3 have no local minimum. It is a single O(n) left-to-right pass.
- ✗Confusing the global minimum with the first local one
- ✗Checking only one neighbour instead of both
- ✗Mishandling the first/last elements as candidates
- →How would you treat endpoints if they were eligible?
- →What is the time complexity of your scan?
A local minimum is strictly smaller than both neighbours, so only interior positions can qualify. One left-to-right pass returns the first match.
def first_local_min(x: list[int]) -> int | None:
for i in range(1, len(x) - 1):
if x[i] < x[i - 1] and x[i] < x[i + 1]:
return x[i]
return NoneFor [1, 2, 1, 2, 3, 4, 5, 6] index 2 holds 1, which is below both 2s, so the function returns 1. Lists shorter than three elements have no interior position and return None. The scan is O(n) time, O(1) extra space.
