1095. Find in Mountain Array

HardArrayBinary SearchInteractive
Leetcode Link

Problem Description

The problem describes a scenario where you are provided with a special kind of array known as a "mountain array." A mountain array has the following characteristics:

  • It has at least three elements.
  • It first increases strictly until it reaches a peak, where the elements are strictly greater than their adjacent elements.
  • After the peak, the elements decrease strictly.

You cannot access this mountain array directly. Instead, you are given access to a MountainArray interface with two methods:

  • get(k) which returns the element at index k.
  • length() which returns the length of the array.

Your task is to find the minimum index where the target value is located in this mountain array. If the target value does not exist in the mountain array, you should return -1. However, there is a constraint that you cannot make more than 100 calls to the get() method.

Intuition

The solution relies on understanding that a mountain array consists of two sorted parts: an increasing sequence followed by a decreasing sequence. This structure allows the use of binary search twice: once to find the peak of the mountain array, and once to search for the target in each of the sorted parts efficiently.

Here's the step-by-step intuition behind the solution:

  1. We use binary search to find the peak element in the mountain array. At each step, if the mid element is greater than the next element, we are in the descending part, so we move the search to the left. Otherwise, we are in the ascending part, so we move the search to the right.

  2. Once the peak is found, we search for the target in the ascending part of the array from index 0 to the peak index:

    • If the target is present and found, we return the index.
    • If not found, we proceed to step 3.

  3. We then search the descending part of the array from the peak index to the end of the array.

  4. In both searches, our goal is to find the minimum index at which the target appears. Therefore, if we find the target in the ascending part, we can return immediately as no index will be smaller.

  5. If we do not find the target in the ascending part, we continue the search in the descending part.

    • In the ascending part, we use k=1 in the search helper search(l: int, r: int, k: int) to keep the regular binary search condition.
    • In the descending part, we use k=-1 to reverse the condition, effectively implementing a binary search for a descending order.

The key to this approach is the modification of binary search to adapt to both the increasing and decreasing parts of the mountain array.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many ways can you arrange the three letters A, B and C?

Solution Approach

The implementation of the solution involves the use of binary search in two phases. Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until the possible locations are reduced to just one.

Finding the Peak Element

The first phase of the algorithm is to find the peak element of the mountain array using a binary search. Given the nature of the mountain array, the peak is the element where the sequence switches from increasing to decreasing.

Here's how we perform the binary search to find the peak:

  1. Initialize two pointers, l (left) and r (right), to the start and end of the array.
  2. Enter a while loop which continues as long as l is less than r.
  3. Calculate the middle index mid using the formula (l + r) >> 1. The >> 1 is a bitwise operation that divides the sum by two.
  4. If the mid element is greater than the next element (mid + 1), then we know the peak must be to the left, including mid. Therefore, we move the right pointer to mid.
  5. If not, then we know the peak is to the right, so we move the left pointer to mid + 1.
  6. When l equals r, we've found the peak.

Searching the Target in the Sorted Parts

The second phase of the algorithm uses the peak to divide the array into two sorted parts and performs separate binary searches on each.

Here's the process:

  1. First, we perform a binary search on the ascending part of the array. We define a helper function search(l: int, r: int, k: int) to help us with that. The parameters l and r define the search range, and k is a modifier which will be 1 for the ascending part and -1 for the descending part.
  2. In the search function, we continue the binary search pattern as before. We compare the mid element scaled by k to the target also scaled by k. This allows us to perform the search in both ascending and descending parts by changing the comparison conditions accordingly.
  3. If we find the target in the ascending part, we return its index as it's guaranteed to be the minimum index.
  4. If we do not find the target in the ascending part, we perform a binary search on the descending part (from l which is peak + 1 to the end of the array).
  5. Again, we make use of the search helper function but this time with k=-1 to account for the descending order of this part.
  6. Finally, if we find the target, we return the index. If not, we return -1 indicating the target is not present in the mountain array.

The overall time complexity of the algorithm is O(log n) due to the binary search, which makes it highly efficient even for large arrays, as long as the constraints of the number of get calls are respected.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's illustrate the solution approach with an example:

Suppose we have a mountain array [1, 2, 3, 5, 4, 2, 0], where the peak element is 5, and we want to find the target value 2.

Finding the Peak Element

  1. Initialize l = 0 and r = 6 (length of the array - 1).
  2. Enter the while loop: while l < r.
  3. First iteration:
    • mid = (0 + 6) >> 1 = 3.
    • get(3) = 5, get(4) = 4; since get(3) is greater than get(4), the peak is to the left, including mid.
    • Update r = mid = 3.
  4. Next iteration:
    • Now l = 0 and r = 3, mid = (0 + 3) >> 1 = 1.
    • get(1) = 2, get(2) = 3; since get(1) is less than get(2), peak is to the right.
    • Update l = mid + 1 = 2.
  5. Next iteration:
    • Now l = 2 and r = 3, mid = (2 + 3) >> 1 = 2.
    • Again, get(2) = 3 is less than get(3) = 5, peak is still to the right.
    • Update l = mid + 1 = 3.
  6. Now l equals r at 3, the loop ends, and we've identified the peak index to be 3.

Searching the Target in the Ascending Part

  1. Perform a binary search on the ascending part, which is from index 0 to 3 (the peak index).
  2. The helper function search is called: search(0, 3, 1) with k=1.
  3. First iteration:
    • mid = (0 + 3) >> 1 = 1.
    • get(1) = 2 equals the target, so we return this index immediately. No need to search the descending part because the found index is guaranteed to be the minimum possible.

Since we are only illustrating the solution approach, we won't search the descending part, as our target has been found in the ascending part at index 1 which is the minimum index possible for our target value 2.

The example above demonstrates the power of binary search in breaking down the problem of finding the target value in a mountain array into a series of logical steps, making the problem manageable and the solution efficient.

Solution Implementation

1class Solution:
2    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
3        # Helper function to perform binary search in the given range (l to r)
4        # and a direction denoted by 'direction_factor' (-1 for descending, 1 for ascending).
5        def binary_search(left: int, right: int, direction_factor: int) -> int:
6            while left < right:
7                mid = (left + right) // 2  # Use '//' for floor division in Python 3
8                # Multiplying by direction_factor to account for ascending or descending order,
9                # based on the part of the mountain array we are searching.
10                if direction_factor * mountain_arr.get(mid) >= direction_factor * target:
11                    right = mid
12                else:
13                    left = mid + 1
14            # Check if we found the target, otherwise return -1.
15            if mountain_arr.get(left) == target:
16                return left
17            else:
18                return -1
19
20        # Find the peak of the mountain array where the next element is smaller than the current.
21        n = mountain_arr.length()
22        left, right = 0, n - 1
23        while left < right:
24            mid = (left + right) // 2
25            # If the mid element is greater than the next element, the peak is on the left.
26            if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
27                right = mid
28            else:
29                left = mid + 1
30        peak = left
31      
32        # First, we search the ascending part of the mountain array.
33        result = binary_search(0, peak, 1)
34        # If target is not found in the ascending part, search the descending part.
35        if result == -1:
36            result = binary_search(peak + 1, n - 1, -1)
37        return result
38
1class Solution {
2
3    private MountainArray mountainArray;
4    private int targetValue;
5
6    public int findInMountainArray(int target, MountainArray mountainArr) {
7        this.mountainArray = mountainArr;
8        this.targetValue = target;
9
10        int n = mountainArray.length();
11        // Find the peak of the mountain array
12        int peakIndex = findPeakIndex(0, n - 1);
13      
14        // First, try to find the target in the ascending part
15        int index = binarySearch(0, peakIndex, 1);
16      
17        // If the target is not found in the ascending part, search in the descending part
18        if (index == -1) {
19            index = binarySearch(peakIndex + 1, n - 1, -1);
20        }
21      
22        return index;
23    }
24
25    // Use binary search to find the peak of the mountain
26    private int findPeakIndex(int left, int right) {
27        while (left < right) {
28            int mid = (left + right) >>> 1;
29            if (mountainArray.get(mid) > mountainArray.get(mid + 1)) {
30                right = mid;
31            } else {
32                left = mid + 1;
33            }
34        }
35        // Left and right converge to peak index
36        return left;
37    }
38
39    // Modified binary search to handle ascending or descending order
40    private int binarySearch(int left, int right, int direction) {
41        while (left <= right) {
42            int mid = (left + right) >>> 1;
43            int midValue = mountainArray.get(mid);
44            if (midValue == targetValue) {
45                return mid;
46            }
47          
48            if ((midValue < targetValue) == (direction > 0)) {
49                left = mid + 1; // Ascending and target is larger or descending and target is smaller
50            } else {
51                right = mid - 1;
52            }
53        }
54        return -1; // Target is not found within the search space
55    }
56}
57
1class Solution {
2public:
3    int findInMountainArray(int target, MountainArray& mountainArr) {
4        // First, find the peak of the mountain array. A peak element is an element that is greater
5        // than its neighbors. Here, we use a binary search approach to find the peak.
6        int n = mountainArr.length();
7        int left = 0, right = n - 1;
8        while (left < right) {
9            int mid = left + (right - left) / 2;
10            // Compare middle element with its next element to determine the direction of the peak
11            if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
12                // If middle element is greater than the next, the peak is to the left
13                right = mid;
14            } else {
15                // If the next element is greater, the peak is to the right
16                left = mid + 1;
17            }
18        }
19
20        // Once the peak is found, use binary search for the target
21        // in the increasing part of the mountain array
22        int peak = left;
23        int index = binarySearch(mountainArr, 0, peak, target, 1);
24        if (index != -1) {
25            // If the target is found in the increasing part, return the index
26            return index;
27        } else {
28            // If the target was not found in the increasing part, then 
29            // use binary search in the decreasing part of the mountain array
30            return binarySearch(mountainArr, peak + 1, n - 1, target, -1);
31        }
32    }
33  
34private:
35    // Helper function to perform binary search 
36    // The 'direction' parameter is used to handle both increasing (1) and decreasing (-1) parts
37    int binarySearch(MountainArray& mountainArr, int left, int right, int target, int direction) {
38        while (left <= right) {
39            int mid = left + (right - left) / 2;
40            int value = mountainArr.get(mid);
41            if (value == target) {
42                return mid;
43            }
44          
45            // Multiply the comparison operands by 'direction' to handle both ascending and descending order.
46            // This allows the function to be used for both sides of the peak.
47            if (direction * value < direction * target) {
48                left = mid + 1;
49            } else {
50                right = mid - 1;
51            }
52        }
53        return -1; // Return -1 if the target is not found
54    }
55};
56
1/**
2 * This function finds a target element within a "mountain" array.
3 * A mountain array is defined as an array where elements increase up to a peak,
4 * after which they decrease.
5 * 
6 * @param target number - The target number to find in the mountain array.
7 * @param mountainArray MountainArray - An instance of MountainArray.
8 * @return number - The index of the target if found, otherwise -1.
9 */
10function findInMountainArray(target: number, mountainArr: MountainArray): number {
11    // Get the length of the mountain array.
12    const arrayLength = mountainArr.length();
13
14    // Initially, set the left and right search bounds to the entire array.
15    let left = 0;
16    let right = arrayLength - 1;
17
18    // Find the peak of the mountain array.
19    while (left < right) {
20        const mid = Math.floor((left + right) / 2);
21
22        // If the middle element is greater than the next one, we are in the decreasing part.
23        if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
24            right = mid;
25        } else {
26            // Otherwise, we are in the increasing part.
27            left = mid + 1;
28        }
29    }
30
31    // After finding the peak, `left` points to the peak element.
32
33    /**
34     * Searches for the target in the specified range of the mountain array.
35     * 
36     * @param start number - The starting index for the search range.
37     * @param end number - The end index for the search range.
38     * @param direction number - The direction of search, 1 for ascending and -1 for descending.
39     * @return number - The index of the target if found, otherwise -1.
40     */
41    const binarySearch = (start: number, end: number, direction: number): number => {
42        while (start < end) {
43            const mid = Math.floor((start + end) / 2);
44            const reversedMidValue = direction * mountainArr.get(mid);
45
46            // Multiply by `direction` to "flip" the comparison in a decreasing array.
47            if (reversedMidValue >= direction * target) {
48                end = mid;
49            } else {
50                start = mid + 1;
51            }
52        }
53
54        // Check if we actually found the target.
55        return mountainArr.get(start) === target ? start : -1;
56    };
57
58    // First try to find the target in the increasing part of the mountain array.
59    const peakIndex = left;
60    const ascResult = binarySearch(0, peakIndex, 1);
61
62    // If not found in the ascending part, try to find it in the descending part.
63    return ascResult === -1 ? binarySearch(peakIndex + 1, arrayLength - 1, -1) : ascResult;
64}
65
Not Sure What to Study? Take the 2-min Quiz：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

Time Complexity

The findInMountainArray method involves two main phases: first finding the peak of the mountain array, and then performing two binary searches, one on the increasing part of the array and one on the decreasing part.

  1. Finding the peak takes O(log n) time, where n is the number of elements in mountain_arr, because a modified binary search is used, which halves the search space at each step.

  2. The binary search on the increasing part and the decreasing part each also take O(log n) time for similar reasons. This gives us two separate O(log n) operations.

Hence, the total time complexity of this function is O(log n) + O(log n), which simplifies to O(log n) considering that constants are dropped in big O notation and log base 2 operations can be considered equivalent in complexity analysis.

Space Complexity

The space complexity is O(1) because we only have a constant number of integer variables, which take up constant space. The space used does not grow with the input size of the mountain_arr.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫