Logicmojo - Updated Aug 28, 2021

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:

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.

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

To begin, set the maximum length to 0.

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

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

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.

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

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.

#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; }

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)); } }

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)