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:
Input: nums = [11, 4, 2, 5, 11, 13, 5]
Output: 2
Example 2:
Input: nums = [1, 2, 3, 4]
Output: 1
Example 3:
Input: nums = [3]
Output: 3
Example 4:
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:
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
Java
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
}
}
Python
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
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.
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.
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.