🚀2. Bitonic Point 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description

Given an array of integers arr[] that is first strictly increasing and then maybe strictly decreasing, find the bitonic point, which is the maximum element in the array.

A Bitonic Point is a point before which elements are strictly increasing and after which elements are strictly decreasing.

🔍 Example Walkthrough

Input:

arr[] = [1, 2, 4, 5, 7, 8, 3]

Output:

8

Explanation: Elements before 8 are strictly increasing [1, 2, 4, 5, 7] and elements after 8 are strictly decreasing [3].

Input:

arr[] = [10, 20, 30, 40, 50]

Output:

50

Explanation: Elements before 50 are strictly increasing [10, 20, 30, 40] and there are no elements after 50.

Input:

arr[] = [120, 100, 80, 20, 0]

Output:

120

Explanation: There are no elements before 120, and elements after 120 are strictly decreasing [100, 80, 20, 0].

Constraints:

• $3 \leq arr.size() \leq 10^5$

• $1 \leq arr[i] \leq 10^6$

🎯 My Approach

Step-by-Step:

1. Problem Understanding:

   • The array is bitonic, meaning it has a single peak, with elements strictly increasing up to that point and strictly decreasing afterward.

   • The task is to find the bitonic point (the maximum value of the array).

2. Binary Search Approach:

   • Since the array has a strict increase followed by a strict decrease, we can use binary search to find the bitonic point in O(log n) time.

   • The idea is to find the middle element and compare it with its neighbors:

     • If the middle element is smaller than its next neighbor, the peak lies on the right side.

     • If the middle element is greater than its next neighbor, the peak lies on the left side or at the middle element itself.

3. Steps:

   • Initialize lo = 0 and hi = arr.size() - 1.

   • While lo < hi:

     • Calculate mid = lo + (hi - lo) / 2.

     • If arr[mid] < arr[mid + 1], move lo = mid + 1 (since the peak is on the right).

     • If arr[mid] > arr[mid + 1], move hi = mid (since the peak is either at mid or to the left).

   • Finally, return arr[lo] which will be the maximum element.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(log n), where n is the size of the array. The algorithm uses binary search, which divides the search space in half at each step.

• Expected Auxiliary Space Complexity: O(1), as the solution uses only a constant amount of additional space (no extra space is required for storing the result or during the search process).

📝 Solution Code

Code (C++)

class Solution {
  public:
    int findMaximum(vector<int> &arr) {
        int lo = 0, hi = arr.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[mid + 1])
                lo = mid + 1;
            else
                hi = mid;
        }
        return arr[lo];
    }
};

Code (Java)

class Solution {
    public int findMaximum(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[mid + 1])
                lo = mid + 1;
            else
                hi = mid;
        }
        return arr[lo];
    }
}

Code (Python)

class Solution:
	def findMaximum(self, arr):
		    lo, hi = 0, len(arr) - 1
		    while lo <= hi:
		        mid = lo + (hi - lo) // 2
		        if mid == 0:
		            return max(arr[0], arr[1])
		        if mid == len(arr) - 1:
		            return max(arr[-1], arr[-2])
		        if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid+1]:
		            return arr[mid]
		        elif arr[mid] > arr[mid - 1]:
		            lo = mid + 1
		        else:
		            hi = mid - 1

📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count