Longest Mountain in Array

Problem

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Examples

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.

Constraints

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

Follow up:

• Can you solve it using only one pass?
• Can you solve it in O(1) space?

Solution

Method 1 – Two Pointers (1)

Intuition

A mountain must strictly increase then strictly decrease. We can use two pointers to find the start and end of each mountain and track the maximum length.

Approach

1. Initialize a variable to track the maximum mountain length (ans).
2. Iterate through the array:
   • For each index, find the start of an increasing sequence.
   • Continue while the sequence is strictly increasing.
   • If a peak is found, continue while the sequence is strictly decreasing.
   • If a valid mountain is found (length ≥ 3), update ans.
   • Move the pointer to the end of the current mountain.
3. Return ans if any mountain is found, else 0.

Code

C++

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size(), ans = 0, i = 1;
        while (i < n-1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                int l = i, r = i;
                while (l > 0 && arr[l-1] < arr[l]) l--;
                while (r+1 < n && arr[r] > arr[r+1]) r++;
                ans = max(ans, r-l+1);
                i = r;
            } else {
                i++;
            }
        }
        return ans;
    }
};

Go

func longestMountain(arr []int) int {
    n, ans, i := len(arr), 0, 1
    for i < n-1 {
        if arr[i-1] < arr[i] && arr[i] > arr[i+1] {
            l, r := i, i
            for l > 0 && arr[l-1] < arr[l] { l-- }
            for r+1 < n && arr[r] > arr[r+1] { r++ }
            if r-l+1 > ans { ans = r-l+1 }
            i = r
        } else {
            i++
        }
    }
    return ans
}

Java

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length, ans = 0, i = 1;
        while (i < n-1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                int l = i, r = i;
                while (l > 0 && arr[l-1] < arr[l]) l--;
                while (r+1 < n && arr[r] > arr[r+1]) r++;
                ans = Math.max(ans, r-l+1);
                i = r;
            } else {
                i++;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun longestMountain(arr: IntArray): Int {
        val n = arr.size
        var ans = 0
        var i = 1
        while (i < n-1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                var l = i
                var r = i
                while (l > 0 && arr[l-1] < arr[l]) l--
                while (r+1 < n && arr[r] > arr[r+1]) r++
                ans = maxOf(ans, r-l+1)
                i = r
            } else {
                i++
            }
        }
        return ans
    }
}

Python

class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        n = len(arr)
        ans = i = 1
        res = 0
        while i < n-1:
            if arr[i-1] < arr[i] > arr[i+1]:
                l = i
                r = i
                while l > 0 and arr[l-1] < arr[l]:
                    l -= 1
                while r+1 < n and arr[r] > arr[r+1]:
                    r += 1
                res = max(res, r-l+1)
                i = r
            else:
                i += 1
        return res

Rust

impl Solution {
    pub fn longest_mountain(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut ans = 0;
        let mut i = 1;
        while i < n-1 {
            if arr[i-1] < arr[i] && arr[i] > arr[i+1] {
                let mut l = i;
                let mut r = i;
                while l > 0 && arr[l-1] < arr[l] { l -= 1; }
                while r+1 < n && arr[r] > arr[r+1] { r += 1; }
                ans = ans.max(r-l+1);
                i = r;
            } else {
                i += 1;
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    longestMountain(arr: number[]): number {
        const n = arr.length;
        let ans = 0, i = 1;
        while (i < n-1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                let l = i, r = i;
                while (l > 0 && arr[l-1] < arr[l]) l--;
                while (r+1 < n && arr[r] > arr[r+1]) r++;
                ans = Math.max(ans, r-l+1);
                i = r;
            } else {
                i++;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of arr. Each index is visited at most twice.
• 🧺 Space complexity: O(1), only a few variables are used.