Find in Mountain Array (Binary Search)

Round 1

Questions: You are given a mountain array, which is an array that satisfies the following conditions:

• The array has at least three elements.
• There exists a peak element, such that all elements to the left are strictly smaller, and all elements to the right are strictly smaller.
• You need to find a target element in the mountain array and return its index. If the target does not exist in the array, return -1.

Implement the function:

public int findInMountainArray(int target, MountainArray mountainArr);

Where:

• mountainArr.get(index) is an API call that returns the value at the specified index.
• mountainArr.length() is an API call that returns the length of the mountain array.

Example 1

Input:

mountainArr = [1, 2, 3, 4, 5, 3, 1]
target = 3

Output:

3
Explanation: The target 3 is present in the array at index 3.

Example 2

Input:

mountainArr = [1, 2, 3, 4, 5, 3, 1]
target = 6

Output:

-1
Explanation: The target 6 is not present in the array.

Solution Explanation

To solve the problem, we perform the following steps:

1. Find the Peak
Use a binary search to find the peak element. This is the element in the middle of the array where the element on the left is smaller and the element on the right is smaller.

2. Binary Search on the Left (Ascending Part)
Once the peak is found, use binary search to search the left portion of the array (where the elements are strictly increasing).

3. Binary Search on the Right (Descending Part)
If the target is not found in the left part, use binary search on the right portion (where the elements are strictly decreasing).

Time Complexity

Finding the peak takes O(log N).
Performing binary search in both the left and right parts also takes O(log N). Thus, the total time complexity is O(log N).

Code Implementation

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // Step 1: Find the peak index
        int peak = peakValue(mountainArr);
        
        // Step 2: Search in the left (ascending) part
        int firstTry = binarySearch(mountainArr, target, 0, peak, true);
        if (firstTry != -1) {
            return firstTry;
        }
        
        // Step 3: Search in the right (descending) part
        return binarySearch(mountainArr, target, peak + 1, mountainArr.length() - 1, false);
    }

    // Binary Search function for both ascending and descending parts
    private int binarySearch(MountainArray mountainArr, int target, int start, int end, boolean isAsc) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int midValue = mountainArr.get(mid); // API call
            
            if (midValue == target) {
                return mid;
            }
            
            if (isAsc) { // Ascending order
                if (target > midValue) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else { // Descending order
                if (target > midValue) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }

    // Find the peak index in the mountain array
    private int peakValue(MountainArray mountainArr) {
        int start = 0;
        int end = mountainArr.length() - 1;
        
        while (start < end) {
            int mid = start + (end - start) / 2;
            int midValue = mountainArr.get(mid);
            int nextValue = mountainArr.get(mid + 1); // Only one additional API call
            
            if (midValue < nextValue) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start; // Peak index
    }
}

Conclusion

• The approach efficiently handles searching in a mountain array by first finding the peak and then performing binary searches in both the ascending and descending parts.
• The algorithm runs in O(log N) time, which is optimal for this problem.

---