Problem

Given an array that is either first increasing and then decreasing (bitonic or mountain array), or first decreasing and then increasing (valley-shaped array):

  • If the array is first increasing and then decreasing, find the peak element.
  • If the array is first decreasing and then increasing, find the valley (minimum) element.

Examples

Example 1:

1
2

Input: arr = [2, 4, 6, 8, 10, 3, 1]
Output: 4

Example 2:

1
2

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

Solution

Method 1 - Binary Search

Here is the approach:

  1. Initialize the Search:
    • Use a binary search to find the critical point in the array.
    • At each step, compute the middle index mid.
  2. Binary Search:
    • Compare arr[mid] with its neighbours:
      • If the array is bitonic, the middle element arr[mid] will be greater than arr[mid + 1] in the peak region. Adjust the pointers to search in the left half (including mid).
      • If the array is valley-shaped, the middle element arr[mid] will be smaller than arr[mid + 1] in the valley region. Adjust the pointers to search in the right half (including mid).
  3. Termination:
    • Continue refining the search range until left meets right, at which point, left or right will point to the critical element (peak or valley).

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

class Solution {
    public int findCriticalPoint(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]) {
                // Peak must be in the left half, including mid
                right = mid;
            } else {
                // Valley must be in the right half, excluding mid
                left = mid + 1;
            }
        }

        // Left (or right) will be the index of the critical element
        return left;
    }

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

        int[] bitonicArray = {1, 3, 8, 12, 4, 2}; // Increasing then decreasing
        System.out.println(sol.findCriticalPoint(bitonicArray)); // Output: 12

        int[] valleyArray = {12, 8, 4, 2, 3, 10}; // Decreasing then increasing
        System.out.println(sol.findCriticalPoint(valleyArray)); // Output: 2
    }
}
 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

from typing import List


class Solution:
    def findCriticalPoint(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:
                # Valley must be in the right half, excluding mid
                left = mid + 1

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


# Example usage
sol = Solution()
bitonicArray = [1, 3, 8, 12, 4, 2]  # Increasing then decreasing
print(sol.findCriticalPoint(bitonicArray))  # Output: 12

valleyArray = [12, 8, 4, 2, 3, 10]  # Decreasing then increasing
print(sol.findCriticalPoint(valleyArray))  # Output: 2

Complexity

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