# 845. Longest Mountain in Array

Reference: LeetCode
Difficulty: Medium

## Problem

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.

Note:

• 0 <= A.length <= 10000
• Indicate that $O(N^2)$ is not okay.
• 0 <= A[i] <= 10000

Example:

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

## Analysis

### Brute-Force

For an array of size $n$, we compute the mountain lengths for every subarray from size at least 3 to n.

Note: Be very careful about the index update.

In terms of the mountain length calculation (the mountain should start from the first element), check out the examples in comments. The following code is similar to the one-pointer solution.

Time: $O(N^3)$ (unacceptable)
Space: $O(1)$

### One-Pass (one pointer)

By observation of the example below, we can actually go through the array and get the maximum mountain length in one pass.

In order to do that, we have to simulate the going-up and going-down processes in order. For example, while going up, the start point is at 1, the peek is at 3, and the end point is at 5. We cannot go further, so we have a mountain of length 5. We do that for the following mountain until we reach the end of the array.

The idea is not difficult, but the implementation is because of index manipulation and special/corner cases. Try to come up with some small examples and get some invariants.

Note:

• Since we check elements at A[i] and A[i + 1], the condition is i < n - 1.
• Record the starting point in each process, reconstruct a new mountain if i does not move at all (which means invalidity).
• Go through your code for cases: [1,2,2], [2], [1,2,3], [3,2,1].

Time: $O(N)$
Space: $O(1)$

### DP

Use extra two arrays inc[] and dec[] to store information we need and then go through the array.

• inc[i]: The maximum increasing length for the subarray ending at i. (constructed from left)
• For example: [1,2,3] the inc[i] = [0,1,2].
• dec[i]: The maximum decreasing length for the subarray starting at i. (constructed from right)
• Both inc[] and dec[] are initialized with $0$.

Then we go through the array from 1 to n - 1 for each possible peak. We calculate the peak only when inc[i] and dec[i] are both non-zero.

Note: The length is inc[i] + dec[i] + 1.

Here is the code:

Time: $O(N)$
Space: $O(N)$

Comment
Junhao Wang
a software engineering cat