Longest Mountain in Array [Medium] — Two Pass Expand

Problem Statement

A mountain array has at least 3 elements, strict increase then strict decrease. Find the length of the longest mountain.

Input: [2,1,4,7,3,2,5] → Output: 5 ([1,4,7,3,2])

Intuition

Two-pass scan:

up[i] = length of increasing run ending at i
down[i] = length of decreasing run starting at i

Mountain at i: up[i] > 0 and down[i] > 0, length = up[i]+down[i]+1.

Solutions

C++

int longestMountain(vector<int>& A) {
    int n=A.size(), ans=0;
    vector<int> up(n,0),down(n,0);
    for(int i=1;i<n;i++) if(A[i]>A[i-1]) up[i]=up[i-1]+1;
    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(up[i]&&down[i]) ans=max(ans,up[i]+down[i]+1);
    return ans;
}

Python

def longestMountain(arr: list[int]) -> int:
    n = len(arr)
    up = [0]*n; down = [0]*n
    for i in range(1,n):
        if arr[i] > arr[i-1]: up[i] = up[i-1]+1
    for i in range(n-2,-1,-1):
        if arr[i] > arr[i+1]: down[i] = down[i+1]+1
    return max((up[i]+down[i]+1 for i in range(n) if up[i] and down[i]), default=0)

JavaScript

var longestMountain = function(arr) {
    const n=arr.length, up=new Array(n).fill(0), down=new Array(n).fill(0);
    for(let i=1;i<n;i++) if(arr[i]>arr[i-1]) up[i]=up[i-1]+1;
    for(let i=n-2;i>=0;i--) if(arr[i]>arr[i+1]) down[i]=down[i+1]+1;
    let ans=0;
    for(let i=0;i<n;i++) if(up[i]&&down[i]) ans=Math.max(ans,up[i]+down[i]+1);
    return ans;
};

Complexity

Time: O(n), Space: O(n)