Practice/Meta/Find Local Minima in an Array

Find Local Minima in an Array

CodingMust

Problem

You are given an array of distinct integers. A valley element is defined as an element that is strictly smaller than both of its neighbors. For boundary elements (first and last), they are considered valleys if they are smaller than their single neighbor.

Your task is to find and return any one valley element from the array in O(log n) time complexity. If multiple valleys exist, you may return any one of them. You can assume that at least one valley always exists in the given array.

Requirements

1. Implement an efficient algorithm that runs in O(log n) time
2. Return the value of any valley element (not the index)
3. The solution must work for arrays of any size ≥ 1
4. Handle edge cases where valleys appear at array boundaries

Constraints

• 1 ≤ array length ≤ 10^6
• All elements are distinct integers
• -10^9 ≤ array[i] ≤ 10^9
• At least one valley element is guaranteed to exist

Examples

Example 1:

Input: arr = [5, 3, 1, 4, 7] Output: 1 Explanation: The element 1 at index 2 is smaller than both neighbors 3 and 4, making it a valley.

Example 2:

Input: arr = [9, 6, 8, 2, 5, 1, 3] Output: 6 (or 2 or 1) Explanation: Multiple valleys exist: 6 (smaller than 9 and 8), 2 (smaller than 8 and 5), and 1 (smaller than 5 and 3). Any of these is a valid answer.

Example 3:

Input: arr = [1, 2, 3, 4, 5] Output: 1 Explanation: The first element 1 is smaller than its only neighbor 2, so it's a valley.

Example 4:

Input: arr = [10] Output: 10 Explanation: Single element arrays have their only element as the valley.