Last Updated: 22 Nov, 2020
Longest Mountain Subarray
Easy
Asked in companies
You are given an array of 'N' integers denoting the heights of the mountains. You need to find the length of the longest subarray which has the shape of a mountain.
A mountain subarray is defined as a subarray which consists of elements that are initially in ascending order until a peak element is reached and beyond the peak element all other elements of the subarray are in decreasing order.
Example:
If the given array is: [1 3 1 4]. The longest mountain subarray would be 3. This is because the longest mountain is [1 3 1] having length 3.
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first line of each test case contains a single integer 'N' representing the length of the array.
The second line of each test case contains 'N' space-separated integers denoting the elements of the given array.
Output Format:
For each test case, print the length of the longest subarray which has the shape of a mountain in a seperate line.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9
Time Limit : 1 sec
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approaches
- We generate all the possible subarrays by using two nested loops.
- We can run two nested loops, the outer loop picks the starting element and the inner loop picks the ending element.
- The third loop considers all elements in between the starting and ending elements.
- Check if each subarray is a mountain or not. This can be done by checking if the subarray is first strictly increasing and then strictly decreasing.
- Find its length, if it’s a mountain.
- For all subarrays which are mountains, we take the length of the longest one.
- If the length of the given array is less than 3, return 0. This is because if the length of the array is less than 3, mountain would not be possible, since we need the array to be first strictly increasing and then strictly decreasing.
- Use two pointers('START', ‘END’) to find out the longest mountain subarray in the given array.
- When there is increasing subarray, mark the beginning index with the ‘START’ pointer.
- Reset the value of both the ‘START’ and ‘END’ pointer, since it marks the beginning.
- When there is a decreasing subarray, mark the ending index with the ‘END’ pointer.
- Calculate the length of the current subarray ('END' - ‘START’ + 1) and take the maximum of all such lengths.
- Finally return the maximum length that can be achieved.
Similar problems