Problem

Given an array of integer write an algorithm to find the local minima.

OR

Given an array arr of n distinct integers, design an O(log n) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

Definition

An element is considered as local minima if it is less than both of its neighbors (if neighbors exist). Rewriting the problem

Examples

Example 1:

1
2

Input: nums = [11, 4, 2, 5, 11, 13, 5]
Output: 2

Example 2:

1
2

Input: nums = [1, 2, 3, 4]
Output: 1

Example 3:

1
2

Input: nums = [3]
Output: 3

Example 4:

1
2

Input: nums = [6, 4]
Output: 4

Note: There could be many local minima’s, we need to find any one.

Solution

Method 1 - Naive

Use for loop and Go through each element 3 tuples, and compare them. Time Complexity – O(n)

Method 2 - Binary Search Approach

Here is the basic algorithm:

1
2
3
4
5
6
7

 mid = (start + end) / 2;
 1. If there's only one element, it's a local minimum.
 2. If there are two elements, verify each to find the local minimum.
 3. For more elements, check the middle element:
     - If it's a local minimum, return it.
     - If not, one of its adjacent elements must be smaller.
     - Recurse into the half containing the smaller adjacent element, excluding the middle.

Here are the algorithm steps:

  • Verify if the middle element is smaller than its neighbours.
  • If the left neighbour is smaller than the middle element, recursively search the left half of the array.
  • If the right neighbour is smaller than the middle element, recursively search the right half of the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Solution {
    public int findLocalMinima(int[] nums) {
        return binarySearch(nums, 0, nums.length - 1);
    }

    private int binarySearch(int[] nums, int low, int high) {
        if (low == high) {
            return nums[low];
        }

        int mid = (low + high) / 2;

        if ((mid == 0 || nums[mid - 1] > nums[mid]) && (mid == nums.length - 1 || nums[mid + 1] > nums[mid])) {
            return nums[mid];
        } else if (mid > 0 && nums[mid - 1] < nums[mid]) {
            return binarySearch(nums, low, mid - 1);
        } else {
            return binarySearch(nums, mid + 1, high);
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Example 1
        int[] nums1 = {11, 4, 2, 5, 11, 13, 5};
        System.out.println("Local Minima is: " + sol.findLocalMinima(nums1));  // Output: 2

        // Example 2
        int[] nums2 = {1, 2, 3, 4};
        System.out.println(sol.findLocalMinima(nums2));  // Output: 1

        // Example 3
        int[] nums3 = {3};
        System.out.println(sol.findLocalMinima(nums3));  // Output: 3

        // Example 4
        int[] nums4 = {6, 4};
        System.out.println(sol.findLocalMinima(nums4));  // Output: 4
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def findLocalMinima(self, nums):
        def binarySearch(low, high):
            if low == high:
                return nums[low]
            
            mid = (low + high) // 2

            if (mid == 0 or nums[mid - 1] > nums[mid]) and (mid == len(nums) - 1 or nums[mid + 1] > nums[mid]):
                return nums[mid]
            elif mid > 0 and nums[mid - 1] < nums[mid]:
                return binarySearch(low, mid - 1)
            else:
                return binarySearch(mid + 1, high)

        return binarySearch(0, len(nums) - 1)

# Example 1
nums = [11, 4, 2, 5, 11, 13, 5]
sol = Solution()
print(f"Local Minima is: {sol.findLocalMinima(nums)}")  # Output: 2

# Example 2
nums = [1, 2, 3, 4]
print(sol.findLocalMinima(nums))  # Output: 1

# Example 3
nums = [3]
print(sol.findLocalMinima(nums))  # Output: 3

# Example 4
nums = [6, 4]
print(sol.findLocalMinima(nums))  # Output: 4

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Here is the small derivation of time complexity:

T(1) ≤ 1 T(2) ≤ 1 T(n) ≤ T(n / 2) + 1

According to the Master Theorem, this algorithm operates in O(log n) time, as required.

Note

  1. The algorithm finds a single local minimum (LM) in O(log n) time, rather than enumerating all local minima in the array. Since there could be up to n/2 local minima, listing them all in O(log n) time is not feasible.

  2. This method does not ensure the discovery of the global minimum. For example, in the array {8, 5, 4, 3, 1, 2, 6, 9}, the result will be 1, as it is an LM, but not necessarily the global minimum.

  3. The algorithm does not guarantee a specific local minimum. For instance, given the array {8, 5, 4, 3, 6, 4, 5, 1, 2, 6, 4, 5, 9}, the output will be 3, one of the LMs in the array. The LMs present in the array were 3, 4, 1, 4, and the algorithm returned 3 as one of them.