Find the First Array Element Smaller Than Both of Its Neighbors

Given an array of integers, find the first element, scanning from left to right, whose two adjacent neighbors are both strictly larger than it.

Function Signature

def first_dip(nums: list[int]) -> int:

Rules

• The element at index i has two adjacent neighbors only when 0 < i < len(nums) - 1. The first and last elements never qualify.
• The element at index i qualifies when nums[i - 1] > nums[i] and nums[i + 1] > nums[i]. A neighbor equal to the element does not count as larger.
• Return the value of the qualifying element with the smallest index.
• Return -1 if no element qualifies, including when the array has fewer than 3 elements.

Constraints

• 1 <= len(nums) <= 10^5
• 0 <= nums[i] <= 10^9, so the result -1 can never be confused with an element.

Examples

Example 1

Input:  nums = [5, 3, 4, 1, 2]
Output: 3

The element 3 at index 1 has neighbors 5 and 4, both larger. The element 1 at index 3 also qualifies, but it comes later.

Example 2

Input:  nums = [2, 2, 7, 6, 9, 0]
Output: 6

Index 1 does not qualify because its left neighbor 2 is equal, not larger. Index 2 holds 7, which is larger than both of its neighbors. Index 3 holds 6, whose neighbors 7 and 9 are both larger.

Example 3

Input:  nums = [1, 2, 2, 3]
Output: -1

Index 1 has the smaller neighbor 1, and index 2 has the equal neighbor 2, so no element qualifies.

First Element Smaller Than Both Neighbors

Given an array of integers nums, scan it from left to right and find the first element whose two adjacent neighbors are both strictly larger than it.

• The element at index i has two adjacent neighbors only when 0 < i < len(nums) - 1. The first and last elements never qualify.
• The element at index i qualifies when nums[i - 1] > nums[i] and nums[i + 1] > nums[i]. A neighbor equal to the element does not count as larger.
• Return the value of the qualifying element with the smallest index.
• Return -1 if no element qualifies, including when the array has fewer than 3 elements.

Constraints

• 1 <= len(nums) <= 10^5
• 0 <= nums[i] <= 10^9, so the result -1 can never be confused with an element.
• Every value and the result fit in a 32-bit signed integer (none exceeds 2^31 - 1).

Example 1

Input:  nums = [5, 3, 4, 1, 2]
Output: 3

The element 3 at index 1 has neighbors 5 and 4, both larger. The element 1 at index 3 also qualifies, but it comes later.

Example 2

Input:  nums = [2, 2, 7, 6, 9, 0]
Output: 6

Index 1 does not qualify because its left neighbor 2 is equal, not larger. Index 2 holds 7, which is larger than both of its neighbors. Index 3 holds 6, whose neighbors 7 and 9 are both larger.

Hints

1. Only indices strictly between the first and last positions have two neighbors, so the endpoints can never be the answer.
2. Both comparisons are strict: a neighbor equal to the element does not count as larger.
3. When several elements qualify, the answer is decided by position, not by value.

Approach

Scan the interior indices i = 1 .. n - 2 from left to right and return nums[i] at the first index where nums[i - 1] > nums[i] and nums[i + 1] > nums[i]; if the scan finishes without a match, return -1. Invariant: when the scan reaches index i, no interior index before i qualifies, so the first index that passes both strict tests is the smallest qualifying index, and its value is the answer. The endpoints are never tested because each lacks one neighbor. Edge cases: when n < 3 the interior range is empty and the answer is -1; an equal neighbor fails the strict comparison, so plateaus, flat-bottomed valleys and all-equal arrays return -1; since every element is at least 0, a returned 0 is a real dip and -1 is unambiguous. All values are at most 10^9, so 32-bit integers suffice in every language.

• Time complexity: O(n)
• Space complexity: O(1)