Katkat
Back

Find a Local Minimum with Left-Biased Binary Search

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to adapt binary search to identify a local minimum in an unsorted array, focusing on handling boundary conditions and non-strict inequality logic.

Problem Statement

Given an array nums of n integers, a local minimum is defined as an element at index i such that nums[i-1] >= nums[i] <= nums[i+1]. For the boundary elements, a local minimum exists if nums[0] <= nums[1] (for index 0) or nums[n-1] <= nums[n-2] (for index n-1).

Your task is to find the index of any local minimum in the array. You must implement this using a binary search approach to achieve O(log n) time complexity. In the case of multiple local minima or plateaus, return the smallest possible index.

Function Signature

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1: Input: nums = [9, 6, 3, 4, 7] Output: 2 Explanation: nums[2] (3) is less than both nums[1] (6) and nums[3] (4).

Example 2: Input: nums = [1, 2, 3, 4, 5] Output: 0 Explanation: The local minimum is at the boundary index 0.

Edge Cases

  • Single element arrays.
  • Arrays with strictly decreasing or strictly increasing values.
  • Arrays with duplicate values (e.g., [2, 2, 2]).

Hints

Hint 1

Consider the slope between `nums[mid]` and `nums[mid + 1]` to determine which half of the array must contain a local minimum.

Hint 2

If `nums[mid] < nums[mid + 1]`, then a local minimum must exist in the left half, including the `mid` index itself.

Hint 3

If `nums[mid] > nums[mid + 1]`, a local minimum must exist in the right half, specifically in the range `(mid + 1, end)`.

Follow-up questions

  • How does your algorithm handle an array where all elements are equal?
  • Can you modify your approach to find the global minimum in `O(log n)` time if the array is rotated sorted?
  • What changes would be required if the definition of a local minimum were strict (`nums[i-1] > nums[i] < nums[i+1]`)?