# Longest Mountain Subarray

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Longest Mountain Subarray

You are provided an array of 'N' numbers that represent the mountain heights. You must determine the length of the longest subarray with a mountain shape.

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.

Input Format:The first line of input 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.

Ouput Format: print the length of the longest subarray which has the shape of a mountain in a seperate line.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

We have presented two approaches to find the two elements:

• Naive Approach
• Two Pointer Approach

### Approach 1: Naive Approach

Go through every possible sub-array and check whether it is a mountain sub-array or not. This might take a long time to find the solution and the time complexity for the above approach can be estimated as O(N*N) to go through every possible sub-array and O(N) to check whether it is a mountain sub-array or not. Thus, the overall time complexity for the program is O(N3) which is very high.

### Two Pointer Approach

1. If the length of the provided array is less than 3, print 0 because a mountain sub-array is not available in this scenario.

2. To begin, set the maximum length to 0.

3. Find the longest mountain sub-array in the given array using the two-pointer approach ('begin' pointer and'end' pointer).

4. When a increasing sub-array is encountered, set the 'begin' pointer to the beginning index of that increasing sub-array.

5. If an index value is detected in the 'end' pointer, the values in both pointers should be reset because it indicates the start of a new mountain sub-array.

6. Mark the ending index of the mountain sub-array in the 'end' pointer when you come across a decreasing sub-array.

7. Calculate the length of the current mountain sub-array, compare it with the current maximum length of all-mountain sub-arrays traversed until now and keep updating the current maximum length.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int LongestMountain(vector<int>& a)
{
int i = 0, j = -1,
k = -1, p = 0,
d = 0, n = 0;

if (a.size() < 3) {
return 0;
}

for (i = 0; i < a.size() - 1; i++) {

if (a[i + 1] > a[i]) {

if (k != -1) {
k = -1;
j = -1;
}

if (j == -1) {
j = i;
}
}
else {

if (a[i + 1] < a[i]) {

if (j != -1) {
k = i + 1;
}

if (k != -1 && j != -1) {
if (d < k - j + 1) {
d = k - j + 1;
}
}
}

else {
k = -1;
j = -1;
}
}
}

if (k != -1 && j != -1) {
if (d < k - j + 1) {
d = k - j + 1;
}
}
return d;
}

int main()
{
vector<int> d = { 1, 3, 1, 4,
5, 6, 7, 8,
9, 8, 7, 6, 5 };

cout << LongestMountain(d)
<< endl;

return 0;
}
```

Java Implementation:

```import java.io.*;

class Main{

public static int LongestMountain(int a[])
{
int i = 0, j = -1, k = -1, d = 0;
if (a.length < 3)
return 0;

for(i = 0; i < a.length - 1; i++)
{
if (a[i + 1] > a[i])
{

if (k != -1)
{
k = -1;
j = -1;
}

if (j == -1)
j = i;
}
else
{

if (a[i + 1] < a[i])
{

if (j != -1)
k = i + 1;

if (k != -1 && j != -1)
{

if (d < k - j + 1)
d = k - j + 1;
}
}
else
{
k = -1;
j = -1;
}
}
}

if (k != -1 && j != -1)
{
if (d < k - j + 1)
d = k - j + 1;
}
return d;
}

public static void main (String[] args)
{
int a[] = { 1, 3, 1, 4, 5, 6, 7,
8, 9, 8, 7, 6, 5 };

System.out.println(LongestMountain(a));
}
}
```

Python Implementation:

```def LongestMountain(a):
i = 0
j = -1
k = -1
p = 0
d = 0
n = 0

if (len(a) < 3):
return 0

for i in range(len(a) - 1):
if (a[i + 1] > a[i]):

if (k != -1):
k = -1
j = -1

if (j == -1):
j = i
else:
if (a[i + 1] < a[i]):

if (j != -1):
k = i + 1

if (k != -1 and j != -1):

if (d < k - j + 1):
d = k - j + 1
else:
k = -1
j = -1

if (k != -1 and j != -1):
if (d < k - j + 1):
d = k - j + 1

return d

d = [ 1, 3, 1, 4, 5, 6,
7, 8, 9, 8, 7, 6, 5 ]

print(LongestMountain(d))

```

Time Complexity: O(N)

Space Complexity: O(1)

With this article at Logicmojo, you must have the complete idea of solving Merge Largest Mountain Subarray problem.