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

Thinking

A mountain rises strictly then falls strictly, and has length at least \(3\). \(n\le 10^4\), so expanding from every peak works but retraces the same slopes.

\(f[i]\) is the longest ascent ending at \(i\), \(g[i]\) the longest descent starting at \(i\). A peak exists only when both exceed \(1\), and its length is \(f[i]+g[i]-1\).

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)

Thinking

The two arrays can be dropped. Scan from a left base: climb to a peak, descend to the right base, update the answer, then move the left pointer to the current right end.

Positions that cannot form a peak are skipped. Each element is visited a constant number of times.

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