845. Longest Mountain in Array


Problem Description

The problem presents the definition of a "mountain array." An array can be considered a mountain array if it satisfies two conditions:

  1. The length of the array is at least 3.
  2. There exists an index i (0-indexed), which is not at the boundaries of the array (meaning 0 < i < arr.length - 1), where the elements strictly increase from the start of the array to the index i, and then strictly decrease from i until the end of the array. In other words, there is a peak element at index i with the elements on the left being strictly increasing and the elements on the right being strictly decreasing.

The objective is to find the longest subarray within a given integer array arr, which is a mountain, and to return its length. If no such subarray exists, the function should return 0.

Intuition

To solve this problem, we can apply a two-pointer technique. The idea is to traverse the array while maintaining two pointers, l (left) and r (right), that will try to identify the bounds of potential mountain subarrays.

We initialize an answer variable, ans, to keep track of the maximum length found so far.

Here is a step by step breakdown of the process:

  1. Start with a left pointer l at the beginning of the array. The right pointer r initially points to the element next to l.

  2. Identify if there's an increasing sequence starting from l; we know it's increasing if arr[l] < arr[r]. If we don't find an increasing sequence, move the left pointer l to the right's current position for the next iteration.

  3. If we do find an increasing sequence, advance the right pointer r as long as the elements keep increasing to find the peak of the mountain.

  4. Once we find the peak (where arr[r] > arr[r + 1]), check if there is a decreasing sequence after the peak. Keep advancing the right pointer while the sequence is decreasing.

  5. Once we've finished iterating through a decreasing sequence or if we can't find a proper peak, we calculate the length of the mountain subarray (if valid) using the positions of l and r. We update ans with the maximum length found.

  6. After processing a mountain or an increasing sequence without a valid peak, set l to r because any valid mountain subarray must start after the end of the previous one.

  7. Repeat the process until we have checked all possible starting points in the array (l + 2 < n is used to ensure there's room for a mountain structure).

The function then returns the maximum length of any mountain subarray found during the traversal, as stored in ans.

Using this approach, we can find the longest mountain subarray in a single pass through the input array, resulting in an efficient solution with linear time complexity, O(n), as each element is looked at a constant number of times.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The solution leverages a single pass traversal using a two-pointer approach, an algorithmic pattern that's often used to inspect sequences or subarrays within an array, especially when looking for some optimal subrange. No additional data structures are required, keeping the space complexity to O(1). The steps of the algorithm are as follows:

  1. Initialize two pointers, l and r (r = l + 1), and an integer ans to zero which will store the maximum length of a valid mountain subarray.

  2. Walk through the array starting from the first element, using l as the start of a potential mountain subarray:

    • Check if the current element and the next one form an increasing pair. If arr[l] < arr[r], that signifies the start of an upward slope.

    • If an upward slope is detected, move r rightwards as long as arr[r] < arr[r + 1], effectively climbing the mountain.

  3. Once the peak is reached, which happens when you can no longer move r to the right without violating the mountain property (arr[r] < arr[r + 1] no longer holds), check if you can proceed downwards:

    • Ensure that the peak isn't the last element (we need at least one element after the peak for a valid mountain array).

    • If arr[r] > arr[r + 1], then we have a downward slope. Now move r rightwards as long as arr[r] > arr[r + 1].

  4. After climbing up and down the mountain, check if a valid mountain subarray existed:

    • If a peak (greater than the first and last elements of the subarray) and a downward slope were found, update ans to the maximum of its current value and the length of the subarray (r - l + 1).

    • If the downward slope isn't present following the peak, just increment r.

  5. Whether you found a mountain or not, set l to r to start looking for a new mountain. This step avoids overlap between subarrays, as a valid mountain subarray ends before a new one can start.

  6. This process is repeated until l is too close to the end of the array to possibly form a mountain subarray (specifically, when l + 2 >= n), at which point all potential subarrays have been evaluated.

The algorithm ensures we examine each element of the array only a constant number of times as we progressively move our pointers without stepping back except to update l to r. This ensures a linear time complexity, making the solution efficient for large arrays.

Finally, we return ans as the result, which by the end of the traversal will hold the maximum length of the longest mountain subarray found.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small example to illustrate how it works. We will use the following array arr:

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

Now, let's follow the steps of the algorithm:

  1. Initialize pointers l = 0 and r = 1, and ans to 0.

  2. Starting from index 0, we compare arr[l] with arr[r]. Since arr[0] > arr[1], we do not have an upward slope, so we move l to the right and set l to r (now l = 1, r = 2).

  3. We check the elements at arr[l] and arr[r]. Now, arr[1] < arr[2], we have an increasing pair, indicating the start of an upward slope.

  4. We increment r to 3 because arr[2] < arr[3]. We continue this process until arr[3] > arr[4], having found the peak of our mountain.

  5. Now, we check if there is a downward slope. Since arr[3] > arr[4], we continue moving r to the right as long as the numbers keep decreasing. We now increment r again as arr[4] > arr[5]. Lastly, since arr[5] < arr[6], the downward slope ends at index 5.

  6. We have found a valid mountain subarray from indices 1 to 5 with length 5 - 1 + 1 = 5. We update ans to 5 because it is greater than the current value of ans.

  7. After finding this mountain, we set l to the current r value (l = 5) and increment r to l + 1 (now l = 5, r = 6).

  8. However, l + 2 >= arr.length is now true, so we stop our process as no further mountain subarrays can start from the remaining elements.

Through this process, we've found that the longest mountain in arr is [1, 4, 7, 3, 2] with a length of 5. Since we found no longer mountains during our traversal, ans remains 5 and that would be the value returned.

Solution Implementation

1class Solution:
2    def longestMountain(self, arr: List[int]) -> int:
3        length_of_array = len(arr)
4        longest_mountain_length = 0  # This will store the length of the longest mountain found
5      
6        # Start exploring from the first element
7        left_pointer = 0
8      
9        # Iterate over the array to find all possible mountains
10        while left_pointer + 2 < length_of_array:  # The smallest mountain has at least 3 elements
11            right_pointer = left_pointer + 1
12          
13            # Check for strictly increasing sequence
14            if arr[left_pointer] < arr[right_pointer]:
15                # Move to the peak of the mountain
16                while right_pointer + 1 < length_of_array and arr[right_pointer] < arr[right_pointer + 1]:
17                    right_pointer += 1
18              
19                # Check if it's a peak and not the end of the array
20                if right_pointer < length_of_array - 1 and arr[right_pointer] > arr[right_pointer + 1]:
21                    # Move down the mountain
22                    while right_pointer + 1 < length_of_array and arr[right_pointer] > arr[right_pointer + 1]:
23                        right_pointer += 1
24                  
25                    # Update the longest mountain length found so far
26                    mountain_length = right_pointer - left_pointer + 1
27                    longest_mountain_length = max(longest_mountain_length, mountain_length)
28                else:
29                    # If it's not a peak, skip this element
30                    right_pointer += 1
31          
32            # Move the left pointer to start exploring the next mountain
33            left_pointer = right_pointer
34      
35        return longest_mountain_length  # Return the largest mountain length found
36
1class Solution {
2    public int longestMountain(int[] arr) {
3        int length = arr.length;
4        int longestMountainLength = 0; // This will store the length of the longest mountain seen so far.
5      
6        // Iterate over each element in the array to find the mountains.
7        for (int start = 0, end = 0; start + 2 < length; start = end) {
8            end = start + 1; // Reset the end pointer to the next element.
9          
10            // Check if we have an increasing sequence to qualify as the first part of the mountain.
11            if (arr[start] < arr[end]) {
12                // Find the peak of the mountain.
13                while (end + 1 < length && arr[end] < arr[end + 1]) {
14                    ++end;
15                }
16              
17                // Check if we have a decreasing sequence after the peak to qualify as the second part of the mountain.
18                if (end + 1 < length && arr[end] > arr[end + 1]) {
19                    // Descend the mountain until the sequence is decreasing.
20                    while (end + 1 < length && arr[end] > arr[end + 1]) {
21                        ++end;
22                    }
23                    // Update the longest mountain length if necessary.
24                    longestMountainLength = Math.max(longestMountainLength, end - start + 1);
25                } else {
26                    // If not a valid mountain, move to the next position.
27                    ++end;
28                }
29            }
30        }
31      
32        return longestMountainLength; // Return the length of the longest mountain in the array.
33    }
34}
35
1class Solution {
2public:
3    int longestMountain(vector<int>& arr) {
4        int arraySize = arr.size(); // The size of the input array.
5        int longestLength = 0; // This will hold the length of the longest mountain found.
6
7        // Loop over the array to find all possible mountains.
8        for (int startPoint = 0, endPoint = 0; startPoint + 2 < arraySize; startPoint = endPoint) {
9          
10            // Initialize the endPoint for the current mountain.
11            endPoint = startPoint + 1;
12          
13            // Check if the current segment is ascending.
14            if (arr[startPoint] < arr[endPoint]) {
15                // Find the peak of the mountain.
16                while (endPoint + 1 < arraySize && arr[endPoint] < arr[endPoint + 1]) {
17                    ++endPoint;
18                }
19              
20                // Check if there is a descending part after the peak.
21                if (endPoint + 1 < arraySize && arr[endPoint] > arr[endPoint + 1]) {
22                    // Find the end of the descending path.
23                    while (endPoint + 1 < arraySize && arr[endPoint] > arr[endPoint + 1]) {
24                        ++endPoint;
25                    }
26                  
27                    // Calculate the length of the mountain and update the longestLength if necessary.
28                    longestLength = max(longestLength, endPoint - startPoint + 1);
29                } else {
30                    // If there is no descending part, move the endPoint forward.
31                    ++endPoint;
32                }
33            }
34        }
35      
36        // Return the length of the longest mountain found in the array.
37        return longestLength;
38    }
39};
40
1function longestMountain(arr: number[]): number {
2    let arraySize: number = arr.length; // The size of the input array.
3    let longestLength: number = 0; // This will hold the length of the longest mountain found.
4
5    // Loop over the array to find all possible mountains.
6    for (let startPoint: number = 0, endPoint: number = 0; startPoint + 2 < arraySize; startPoint = endPoint) {
7        // Initialize the endPoint for the current mountain.
8        endPoint = startPoint + 1;
9      
10        // Check if the current segment is ascending.
11        if (arr[startPoint] < arr[endPoint]) {
12            // Find the peak of the mountain.
13            while (endPoint + 1 < arraySize && arr[endPoint] < arr[endPoint + 1]) {
14                ++endPoint;
15            }
16          
17            // Check if there is a descending part after the peak.
18            if (endPoint + 1 < arraySize && arr[endPoint] > arr[endPoint + 1]) {
19                // Find the end of the descending path.
20                while (endPoint + 1 < arraySize && arr[endPoint] > arr[endPoint + 1]) {
21                    ++endPoint;
22                }
23              
24                // Calculate the length of the mountain and update the longest Length if necessary.
25                longestLength = Math.max(longestLength, endPoint - startPoint + 1);
26            } else {
27                // If there is no descending part, move the endPoint forward.
28                ++endPoint;
29            }
30        }
31    }
32  
33    // Return the length of the longest mountain found in the array.
34    return longestLength;
35}
36

Time and Space Complexity

Time Complexity

The time complexity of the function longestMountain can be analyzed by examining the while loop and nested while loops. The function traverses the array using pointers l and r. The outer while loop runs while l + 2 < n, ensuring at least 3 elements to form a mountain. The first inner while loop executes when a potential ascending part of a mountain is found (arr[l] < arr[r]) and continues until the peak is reached. The second inner while loop executes if a peak is found and continues until the end of the descending part.

Each element is visited at most twice: once during the ascent and once during the descent. Hence, the main loop has at most O(2n) iterations, which simplifies to O(n) where n is the length of the array.

Space Complexity

The space complexity of the code is O(1), as it uses a constant amount of extra space. The variables n, ans, l, and r do not depend on the input size, and no additional data structures are used that scale with the input size.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:


Recommended Readings

Got a question? Ask the Monster 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.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄