Skip to content

845. Longest Mountain in Array

Description

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.

 

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 <= 104
  • 0 <= arr[i] <= 104

 

Follow up:

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

Solutions

Solution 1: Preprocessing + Enumeration

We define two arrays \(f\) and \(g\), where \(f[i]\) represents the length of the longest increasing subsequence ending at \(arr[i]\), and \(g[i]\) represents the length of the longest decreasing subsequence starting at \(arr[i]\). Then for each index \(i\), if \(f[i] \gt 1\) and \(g[i] \gt 1\), the length of the mountain with \(arr[i]\) as the peak is \(f[i] + g[i] - 1\). We only need to enumerate all \(i\) and find the maximum value.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(arr\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                f[i] = f[i - 1] + 1
        ans = 0
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                g[i] = g[i + 1] + 1
                if f[i] > 1:
                    ans = max(ans, f[i] + g[i] - 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }
        int ans = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (arr[i] > arr[i + 1]) {
                g[i] = g[i + 1] + 1;
                if (f[i] > 1) {
                    ans = Math.max(ans, f[i] + g[i] - 1);
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int f[n];
        int g[n];
        fill(f, f + n, 1);
        fill(g, g + n, 1);
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }
        int ans = 0;
        for (int i = n - 2; ~i; --i) {
            if (arr[i] > arr[i + 1]) {
                g[i] = g[i + 1] + 1;
                if (f[i] > 1) {
                    ans = max(ans, f[i] + g[i] - 1);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestMountain(arr []int) (ans int) {
    n := len(arr)
    f := make([]int, n)
    g := make([]int, n)
    for i := range f {
        f[i] = 1
        g[i] = 1
    }
    for i := 1; i < n; i++ {
        if arr[i] > arr[i-1] {
            f[i] = f[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            g[i] = g[i+1] + 1
            if f[i] > 1 {
                ans = max(ans, f[i]+g[i]-1)
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function longestMountain(arr: number[]): number {
    const n = arr.length;
    const f: number[] = Array(n).fill(1);
    const g: number[] = Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        if (arr[i] > arr[i - 1]) {
            f[i] = f[i - 1] + 1;
        }
    }
    let ans = 0;
    for (let i = n - 2; i >= 0; --i) {
        if (arr[i] > arr[i + 1]) {
            g[i] = g[i + 1] + 1;
            if (f[i] > 1) {
                ans = Math.max(ans, f[i] + g[i] - 1);
            }
        }
    }
    return ans;
}

Solution 2: One Pass (Enumerate Left Base of Mountain)

We can enumerate the left base of the mountain and then search to the right for the right base of the mountain. We can use two pointers \(l\) and \(r\), where \(l\) represents the index of the left base and \(r\) represents the index of the right base. Initially, \(l=0\) and \(r=0\). Then we move \(r\) to the right to find the position of the peak. At this point, we check if \(r\) satisfies \(r + 1 \lt n\) and \(arr[r] \gt arr[r + 1]\). If so, we continue moving \(r\) to the right until we find the position of the right base. At this point, the length of the mountain is \(r - l + 1\). We update the answer and then update the value of \(l\) to \(r\), continuing to search for the next mountain.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(arr\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = l = 0
        while l + 2 < n:
            r = l + 1
            if arr[l] < arr[r]:
                while r + 1 < n and arr[r] < arr[r + 1]:
                    r += 1
                if r < n - 1 and arr[r] > arr[r + 1]:
                    while r < n - 1 and arr[r] > arr[r + 1]:
                        r += 1
                    ans = max(ans, r - l + 1)
                else:
                    r += 1
            l = r
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int ans = 0;
        for (int l = 0, r = 0; l + 2 < n; l = r) {
            r = l + 1;
            if (arr[l] < arr[r]) {
                while (r + 1 < n && arr[r] < arr[r + 1]) {
                    ++r;
                }
                if (r + 1 < n && arr[r] > arr[r + 1]) {
                    while (r + 1 < n && arr[r] > arr[r + 1]) {
                        ++r;
                    }
                    ans = Math.max(ans, r - l + 1);
                } else {
                    ++r;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        for (int l = 0, r = 0; l + 2 < n; l = r) {
            r = l + 1;
            if (arr[l] < arr[r]) {
                while (r + 1 < n && arr[r] < arr[r + 1]) {
                    ++r;
                }
                if (r + 1 < n && arr[r] > arr[r + 1]) {
                    while (r + 1 < n && arr[r] > arr[r + 1]) {
                        ++r;
                    }
                    ans = max(ans, r - l + 1);
                } else {
                    ++r;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func longestMountain(arr []int) (ans int) {
    n := len(arr)
    for l, r := 0, 0; l+2 < n; l = r {
        r = l + 1
        if arr[l] < arr[r] {
            for r+1 < n && arr[r] < arr[r+1] {
                r++
            }
            if r+1 < n && arr[r] > arr[r+1] {
                for r+1 < n && arr[r] > arr[r+1] {
                    r++
                }
                ans = max(ans, r-l+1)
            } else {
                r++
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function longestMountain(arr: number[]): number {
    const n = arr.length;
    let ans = 0;
    for (let l = 0, r = 0; l + 2 < n; l = r) {
        r = l + 1;
        if (arr[l] < arr[r]) {
            while (r + 1 < n && arr[r] < arr[r + 1]) {
                ++r;
            }
            if (r + 1 < n && arr[r] > arr[r + 1]) {
                while (r + 1 < n && arr[r] > arr[r + 1]) {
                    ++r;
                }
                ans = Math.max(ans, r - l + 1);
            } else {
                ++r;
            }
        }
    }
    return ans;
}

Comments