FastPrep
Problem · Array

Find a Deterministic Local Minimum

Learn this problem
● MediumMeta logoMetaFULLTIMEONSITE INTERVIEW
See Meta hiring insights

Problem statement

You are given a non-empty integer array nums. An index i is a local minimum when its value is no greater than each existing neighbor. Treat a missing neighbor outside the array as positive infinity.

Return the index selected by this deterministic binary-search rule:

  1. Search the inclusive range [left,right] and use floor((left+right)/2) as mid.
  2. If nums[mid] is a local minimum, return mid.
  3. Otherwise, if the left neighbor is strictly smaller than nums[mid], continue in the left half.
  4. Otherwise continue in the right half.

This rule handles equal neighbors without requiring a strict local minimum.

Function

findLocalMinimum(nums: int[]) → int

Examples

Example 1

nums = [9,7,3,5,8]return = 2

The first midpoint is index 2, and 3 is no greater than either neighbor.

Example 2

nums = [4]return = 0

The only element has no existing neighbor and is therefore a local minimum.

Example 3

nums = [3,2,2,4]return = 1

Index 1 is the first midpoint and its value is no greater than either neighbor, including the equal value on its right.

Constraints

  • nums is non-empty.
  • Every value fits in a signed 32-bit integer.
  • Equal adjacent values are allowed.

More Meta problems

drafts saved locally
public int findLocalMinimum(int[] nums) {
    // Write your code here.
}
nums[9,7,3,5,8]
expected2
checking account