Solutions

1. Linear Search

O(n) time | O(1) space

Intuition

We can check every element whether it is a local minimum with one loop over the whole array.

Algorithm

Iterate through the loop from the first element to the second to last element with i index.
Check if the element at index i is less than the element at index i + 1 and return i if it is.
When the loop finishes, return the index of the last element.

012345

9 > 7

1 / 5

A naive approach would compare each element with both of its neighbours. But for the first element we should check only the right neighbour as the left neighbour is missing. Then for the second element we do not need to check the left neighbour as we already know that it is greater since otherwise it would be returned. So this way we can compare each element only with the right neighbour at each iteration.

Code

def findLocalMinimum(nums: list[int]) -> int:
    for i in range(len(nums) - 1):
        if nums[i] < nums[i+1]:
            return i
    return len(nums) - 1

/**
 * @param {number[]} nums
 * @returns {number}
 */
var findLocalMinimum = function (nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] < nums[i + 1]) return i
  }
  return nums.length - 1
}

class Solution {
    public int findLocalMinimum(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] < nums[i + 1]) return i;
        }
        return nums.length - 1;
    }
}

2. Binary Search

O(logn) time | O(1) space

Intuition

We can use the binary search technique starting from the middle element instead of checking every element.

If it is a local minimum, both of its neighbours should be greater.

If it is not a local minimum, at least one of its neighbours should be less than it. Then we can focus only on the subarray on the side of the smaller neighbour, as we can guarantee there will be a local minimum eventually.

That subarray either keeps decreasing until the end, where the last element is a local minimum, or a greater element appears somewhere along it, and then the element before that one is a local minimum.

Algorithm

Create left and right integer variables with the start and end indexes of the array as initial values.
Iterate through the loop while left is less than right.
Create mid, the middle index between left and right.
If the value on mid is greater than the value on mid + 1, assign mid + 1 to left, dropping the left part.
Otherwise assign mid to right, dropping the right part.
When the loop finishes, return the left index (which should be equal to right).

mid

012345

left right

4 > 2

1 / 5

A naive approach would be checking if the mid element is a local minimum first, then checking both neighbours to decide which way to move. However, just checking with the right neighbour uses less code and is still correct, as if the element at mid is greater than mid + 1 the local minimum is at the right side, otherwise a local minimum is either the element at mid itself or on the left side.

Code

def findLocalMinimum(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return left

/**
 * @param {number[]} nums
 * @returns {number}
 */
var findLocalMinimum = function (nums) {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] > nums[mid + 1]) left = mid + 1
    else right = mid
  }
  return left
}

class Solution {
    public int findLocalMinimum(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}