Problem

Finding the Minimum Value in a Valley-Shaped Array

Examples

Example 1:

1
2

Input: arr = [12, 8, 4, 2, 3, 10];
Output: 3

Solution

Method 1 - Binary Search

Use a binary search to efficiently find the trough element (the minimum value) in the array.

Steps:

  1. Initialize two pointers, left and right, at the beginning and end of the array.
  2. Perform a binary search:
    • Compute the middle index mid.
    • Compare arr[mid] with arr[mid + 1].
    • If arr[mid] is smaller than arr[mid + 1], it indicates that the trough is on the left half (including mid).
    • Otherwise, the trough is on the right half (excluding mid).
  3. Continue until left meets right. The position left or right will point to the trough element or the minimum value in the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int findMinInValleyArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < arr[mid + 1]) {
                // Trough must be in the left half, including mid
                right = mid;
            } else {
                // Trough must be in the right half, excluding mid
                left = mid + 1;
            }
        }

        // Left (or right) will be the index of the trough element
        return left;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findMaxInBitonicArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1

        while left < right:
            mid = (left + right) // 2

            if arr[mid] > arr[mid + 1]:
                # Peak must be in the left half, including mid
                right = mid
            else:
                # Peak must be in the right half, excluding mid
                left = mid + 1

        # Left (or right) will be the index of the peak element
        return left

Complexity

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