Longest Mountain Subarray

Easy
0/40
Average time to solve is 10m
profile
Contributed by
115 upvotes
Asked in companies
MicrosoftGoldman SachsShareChat

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3
4
1 3 1 4
6
1 3 1 4 3 1
3
3 1 3
Sample Output 1:
3
4
0
Explanation of Input 1:
The first test case is already explained in the problem statement.
The second test case, the given array is: [1 3 1 4 3 1] and the longest mountain would be of length: 4 i.e. 1 4 3 1.
The third test case, the given array is: [3 1 3] and the longest mountain would be of length: 0 since there is no increasing, peak and decreasing subarray.
Sample Input 2:
3
4
4 5 1 3
5
4 5 6 7 8
4
9 3 5 4
Sample Output 2
3
0
3
Hint

Generate all possible subarrays

Approaches (2)
Brute Force (Time Limit Exceed)
  • 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.
Time Complexity

O(N^3), Where ‘N’ is the length of the array.

 

In the worst case, we are generating all the subarray which takes O(N^2) time and for each subarray we are traversing the elements of the subarray to check whether it is mountain or not, Thus overall complexity would be O(N^3).

Space Complexity

O(1),

 

In the worst case, only a constant extra space is required.

Code Solution
(100% EXP penalty)
Longest Mountain Subarray
Full screen
Console