Find a Local Minimum in One and Two Dimensions

Problem Statement

A local minimum in an array or grid is an element that is strictly less than all of its adjacent neighbors. Assume all elements in the input are distinct, which guarantees that at least one local minimum always exists.

You are tasked with implementing two functions:

1. find_local_min_1d(arr: list[int]) -> int: Returns the index i of any local minimum in a 1D array. An element arr[i] is a local minimum if it is strictly smaller than its existing neighbors (arr[i-1] if i > 0, and arr[i+1] if i tuple[int, int]: Returns the coordinate (r, c) of any local minimum in an n x m matrix. An element matrix[r][c] is a local minimum if it is strictly smaller than its orthogonal neighbors (up, down, left, right, where they exist). Must run in O(n log m) or O(n + m) time.

Function Signatures

def find_local_min_1d(arr: list[int]) -> int:
    pass

def find_local_min_2d(matrix: list[list[int]]) -> tuple[int, int]:
    pass

Input & Output

• arr: A 1D list of integers of length n where n >= 1.
• matrix: A 2D list of integers of shape n x m where n >= 1 and m >= 1.
• Output for 1D: A valid 0-based index i.
• Output for 2D: A valid 0-based coordinate (r, c).
• If multiple local minima exist, returning any valid one is acceptable.

Constraints

• 1 <= n, m <= 200,000
• For 2D: 1 <= n * m <= 1,000,000
• -10^9 <= arr[i], matrix[r][c] <= 10^9
• All elements within an input array or matrix are pairwise distinct.

Examples

Example 1 (1D)

Input: arr = [9, 7, 8, 5, 6, 4, 10]
Output: 1  # arr[1] = 7 is smaller than arr[0]=9 and arr[2]=8.
           # Note: 3 (arr[3]=5) or 5 (arr[5]=4) are also valid answers.

Example 2 (2D)

Input: matrix = [
    [10,  8, 11, 15],
    [ 9,  6,  7, 14],
    [12, 13,  5,  3],
    [16, 17,  4,  2]
]
Output: (3, 3)  # matrix[3][3] = 2 is smaller than matrix[2][3]=3 and matrix[3][2]=4.
                # (1, 1) is also valid (6 < 8, 9, 7, 13).

Edge Cases

• Single element (n = 1 or 1 x 1): Trivally a local minimum.
• Monotonically increasing or decreasing sequences: The minimum lies on an outer boundary.
• Narrow matrices (1 x m or n x 1): Should degenerate gracefully to the 1D search logic.