Longest Mountain Subarray

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:

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.

#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)