Leetcode 845: Longest Mountain in Array
Given an integer array
arr, you need to find the length of the longest subarray that forms a mountain. A mountain subarray has the following properties: it must have at least three elements, the elements strictly increase to a peak, and then strictly decrease after the peak. If no such subarray exists, return 0.Problem
Approach
Steps
Complexity
Input: You are given an integer array `arr` containing non-negative integers.
Example: Input: arr = [1, 3, 2, 4, 7, 5, 3]
Constraints:
• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4
Output: Return the length of the longest mountain subarray. If no valid mountain exists, return 0.
Example: Output: 5
Constraints:
• The array must have at least 3 elements to form a valid mountain.
Goal: The goal is to find the longest subarray in the form of a mountain. A peak must be surrounded by strictly increasing and strictly decreasing elements.
Steps:
• Step 1: Traverse through the array and calculate the length of the subarray before and after each peak.
• Step 2: For each peak, calculate how far the elements on the left strictly increase and how far the elements on the right strictly decrease.
• Step 3: Keep track of the longest mountain found and return its length.
Goal: The solution should handle arrays with lengths up to 10^4 efficiently, ensuring that the peak and its surroundings strictly increase and decrease.
Steps:
• The array must contain at least 3 elements to form a mountain.
• There should be a peak element where arr[i-1] < arr[i] > arr[i+1].
Assumptions:
• The array is not empty and contains valid integers.
• The array elements are non-negative.
• Input: Input: [1, 3, 2, 4, 7, 5, 3]
• Explanation: The longest mountain is [3, 2, 4, 7, 5], which has length 5.
• Input: Input: [1, 2, 3, 4]
• Explanation: There is no mountain because the array only increases.
• Input: Input: [8, 7, 6, 5]
• Explanation: There is no mountain because the array only decreases.
Approach: We will calculate the length of the longest mountain using two passes through the array. In the first pass, we compute the lengths of increasing and decreasing subsequences from each peak, and in the second pass, we identify the longest mountain.
Observations:
• The mountain is defined by a peak with elements strictly increasing before and strictly decreasing after it.
• We can calculate the lengths of increasing and decreasing subsequences for each potential peak.
• We can compute the lengths of increasing and decreasing sequences for each element and then use this information to calculate the mountain size.
Steps:
• Step 1: Traverse the array and calculate the lengths of increasing subsequences before each element.
• Step 2: Traverse the array in reverse and calculate the lengths of decreasing subsequences after each element.
• Step 3: For each element, if both the increasing and decreasing subsequences have a non-zero length, compute the mountain length as the sum of these two lengths plus one.
• Step 4: Return the maximum length of the mountain.
Empty Inputs:
• The input cannot be empty since the array must have at least 3 elements to form a valid mountain.
Large Inputs:
• Ensure that the solution handles large inputs efficiently (up to 10^4 elements).
Special Values:
• Arrays with all equal elements cannot form a mountain.
• An array that only increases or only decreases does not form a valid mountain.
Constraints:
• The solution must operate in linear time to handle the maximum array length efficiently.
int longestMountain(vector<int>& arr) {
int res = 0;
int n = arr.size();
if(n < 3) return 0;
vector<int> pre(n, 0), suf(n, 0);
int cur = 0;
for(int i = 1; i < n; i++) {
if(arr[i] > arr[i - 1])
cur++;
else cur = 0;
pre[i] = cur;
}
cur = 0;
for(int i = n - 2; i >= 0; i--) {
if(arr[i] > arr[i + 1])
cur++;
else cur = 0;
suf[i] = cur;
}
for(int i = 0; i < n; i++)
if(pre[i] > 0 && suf[i] > 0)
res = max(pre[i] + suf[i] + 1, res);
return res == 1? 0: res;
}
1 : Function Declaration
int longestMountain(vector<int>& arr) {
This is the function declaration where the longestMountain function is defined. It takes a reference to a vector of integers as input and returns an integer.
2 : Variable Initialization
int res = 0;
The result variable 'res' is initialized to 0. This will store the length of the longest mountain.
3 : Variable Initialization
Empty line for readability.
4 : Array Size Calculation
int n = arr.size();
The size of the array 'arr' is calculated and stored in variable 'n'.
5 : Conditional Check
if(n < 3) return 0;
If the array size is less than 3, return 0 as a valid mountain cannot exist.
6 : Array Initialization
vector<int> pre(n, 0), suf(n, 0);
Two vectors 'pre' and 'suf' are initialized to store the lengths of increasing and decreasing sequences.
7 : Variable Initialization
int cur = 0;
The variable 'cur' is initialized to 0. It will be used to track the current length of increasing or decreasing sequences.
8 : Loop Start
for(int i = 1; i < n; i++) {
Loop starts to fill the 'pre' vector with the lengths of increasing sequences from the left.
9 : Conditional Check
if(arr[i] > arr[i - 1])
If the current element is greater than the previous element, it is part of an increasing sequence.
10 : Increment Variable
cur++;
Increment the 'cur' variable to track the length of the increasing sequence.
11 : Reset Variable
else cur = 0;
If the current element is not greater than the previous, reset 'cur' to 0.
12 : Array Update
pre[i] = cur;
Store the current length of the increasing sequence in the 'pre' array.
13 : Variable Reset
cur = 0;
Reset 'cur' to 0 for the second loop.
14 : Loop Start
for(int i = n - 2; i >= 0; i--) {
Second loop starts to fill the 'suf' array with the lengths of decreasing sequences from the right.
15 : Conditional Check
if(arr[i] > arr[i + 1])
If the current element is greater than the next element, it is part of a decreasing sequence.
16 : Increment Variable
cur++;
Increment the 'cur' variable to track the length of the decreasing sequence.
17 : Reset Variable
else cur = 0;
If the current element is not greater than the next, reset 'cur' to 0.
18 : Array Update
suf[i] = cur;
Store the current length of the decreasing sequence in the 'suf' array.
19 : Loop Start
for(int i = 0; i < n; i++)
Loop through the array to check if both 'pre[i]' and 'suf[i]' are greater than 0, indicating a valid mountain.
20 : Conditional Check
if(pre[i] > 0 && suf[i] > 0)
Check if both increasing and decreasing sequences are present at the current index.
21 : Update Result
res = max(pre[i] + suf[i] + 1, res);
Update the result with the maximum length of the mountain found.
22 : Return Statement
return res == 1? 0: res;
Return the result. If the mountain length is 1, return 0, as it doesn't meet the criteria of a mountain.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we traverse the array twice: once for increasing subsequences and once for decreasing subsequences.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the lengths of increasing and decreasing subsequences in separate arrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus