# Solution For Longest Mountain In Array

Problem Statement:

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3

There exists some 0 < i < B.length – 1 such that B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length – 1] (Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain. Return 0 if there is no mountain.

Example 1:

Input: [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: [2,2,2]
Output: 0

Explanation: There is no mountain.

Solution:

The idea is to find all possible peaks and then calculate the corresponding mountain lengths. We can use two pointers to find every peak in the array. A peak is a point in the array such that its left side values are strictly increasing and its right side values are strictly decreasing. We can iterate through the array and whenever we find a peak, we can calculate the length of the mountain as the sum of its left and right side lengths (the left and right sides of the peak).

Algorithm:

Initialize two pointers, left and right, to index 1 and move them to find the first peak of the mountain.

If there is no peak, return 0.

Otherwise, initialize the variable length to 3 (the length of the peak).

Move the left pointer to the left to find the left side of the mountain (which should be strictly increasing).

Increase the length of the mountain by 1 for each number we encounter while moving the left pointer.

Move the right pointer to find the right side of the mountain (which should be strictly decreasing).

Increase the length of the mountain by 1 for each number we encounter while moving the right pointer.

If both left and right pointers reach the end of the array or have not moved, return the length of the mountain. Otherwise, repeat steps 2-6 starting from the right pointer’s current position.

Pseudo code:

int longestMountain(vector

int n = A.size();

int ans = 0, left, right;

for (int i = 1; i < n-1;) {

if (A[i] > A[i-1] && A[i] > A[i+1]) {

left = i-1;

right = i+1;

while (left > 0 && A[left] > A[left-1]) {

left–;

}

while (right < n-1 && A[right] > A[right+1]) {

right++;

}

ans = max(ans, right-left+1);

i = right;

} else {

i++;

}

}

return ans;

}

Time Complexity: O(n) – we iterate through the array at most twice.

Space Complexity: O(1) – we use only constant space for variables.

## Step by Step Implementation For Longest Mountain In Array

public int longestMountain(int[] A) { int N = A.length, res = 0; int[] up = new int[N], down = new int[N]; for (int i = N - 2; i >= 0; --i) if (A[i] > A[i + 1]) down[i] = down[i + 1] + 1; for (int i = 0; i < N; ++i) { if (i > 0 && A[i] > A[i - 1]) up[i] = up[i - 1] + 1; if (up[i] > 0 && down[i] > 0) res = Math.max(res, up[i] + down[i] + 1); } return res; }

def longestMountain(A): # keep track of longest mountain length longest = 0 # iterate through array for i in range(1, len(A)-1): # check if current index is the start of a mountain if A[i] > A[i-1] and A[i] > A[i+1]: # keep track of mountain length mountain_length = 1 # check left side of mountain left = i-1 while left > 0 and A[left] < A[left-1]: mountain_length += 1 left -= 1 # check right side of mountain right = i+1 while right < len(A)-1 and A[right] < A[right+1]: mountain_length += 1 right += 1 # update longest mountain length if necessary longest = max(longest, mountain_length) return longest

var longestMountain = function(A) { let max = 0; let i = 1; while (i < A.length - 1) { let up = 0; let down = 0; // check if there is an upward trend if (A[i] > A[i-1]) { up++; // check for a downward trend while (i+1 < A.length && A[i] > A[i+1]) { down++; i++; } // check if this is a valid mountain if (down > 0 && A[i] < A[i-1]) { max = Math.max(max, up+down+1); } } i++; } return max; };

class Solution { public: int longestMountain(vector& A) { int N = A.size(), res = 0, up = 0, down = 0; for (int i = 1; i < N; ++i) { if (down && A[i - 1] < A[i] || A[i - 1] == A[i]) up = down = 0; up += A[i - 1] < A[i]; down += A[i - 1] > A[i]; if (up && down) res = max(res, up + down + 1); } return res; } };

public int LongestMountain(int[] A) { // edge case if (A.Length < 3) return 0; int longest = 0; int up = 0; int down = 0; for (int i = 1; i < A.Length; i++) { // reset if we hit a plateau if (down > 0 && A[i - 1] < A[i] || A[i - 1] == A[i]) { up = 0; down = 0; } // we are going up! if (A[i - 1] < A[i]) { up++; } // we are going down! if (A[i - 1] > A[i]) { down++; } // if we hit a peak if (up > 0 && down > 0) { longest = Math.Max(longest, up + down + 1); } } return longest; }