Reference: LeetCode
Difficulty: Medium

My Post: [Java] B-F, One-Pass, DP Solutions with Explanations (easy-understand)

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: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: [2,2,2] or [1,2,2]
Output: 0
Explanation: There is no mountain.

Input: [1,2,3]
Output: 0

Input: [2,1,4,7,3,2,5]
          --------- 5
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Input: [2,1,4,7,3,2,3,7,6,5,1]
          --------- 5
                  ----------- 6
Output: 6

Follow up:

  • 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.

1
2
3
4
5
6
7
8
9
10
11
public int longestMountain(int[] A) {
  int n = A.length;
  int maxLen = 0;
  for (int len = 3; len <= n; ++len) {
    for (int i = 0; i + len - 1 < n; ++i) {
      int end = i + len - 1;
      maxLen = Math.max(maxLen, mountainLen(A, i, end));
    }
  }
  return maxLen;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int mountainLen(int[] A, int lo, int hi) {
  int n = hi - lo + 1;
  if (n < 3) {
    return 0;
  }
  // 5 4 3 2 1    -> no mountain
  //   i
  // 1 2 3 4 5    -> no mountain
  //   i       i
  // 1 2 3 2 1    -> returns i = n
  //   i   i   i
  // 1 2 3 2 1 2  -> returns i = n - 1 (not includes the last element)
  //   i   i   i 
  int i = lo + 1;
  while (i <= hi && A[i - 1] < A[i]) {
    ++i;
  }
  if (i == lo + 1 || i == hi + 1) return 0; // no mountain
  // i now points to the first element that A[i - 1] > A[i]
  while (i <= hi && A[i - 1] > A[i]) {
    ++i;
  }
  return i - lo;
}

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.

1
2
3
4
 0 1 2 3 4 5 6 7 8 9 10
[2,1,4,7,3,2,3,7,6,5,1]
   --------- 5
           ----------- 6

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].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int longestMountain(int[] A) {
  int n = A.length;
  int maxLen = 0;
  int i = 0;
  while (i < n - 1) {
    int upStart = i;
    // Go up
    while (i < n - 1 && A[i] < A[i + 1]) ++i;
    if (i == upStart) { // does not move
      ++i; continue;
    } // i stops the peek
    // Go down
    int downStart = i;
    while (i < n - 1 && A[i] > A[i + 1]) ++i;
    if (i == downStart) {
      ++i; continue;
    } // i stops at the last in the subarray
    // Update length
    int len = i - upStart + 1;
    maxLen = Math.max(maxLen, len);
  }
  return maxLen;
}

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.

1
2
3
4
5
6
7
8
// inc[] and inc[] are initialized with 0
index    0   1   2   3   4   5   6   7   8   9   10
------------------------------------------------------
         2   1   4   7   3   2   3   7   6   5   1
inc[i]   0   0   1   2   0   0   1   2   0   0   0
dec[i]   0   0   0   2   1   0   0   3   2   1   0
------------------------------------------------------
len          0   0 4+1=5 0   0   0 5+1=6 0   0   0

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestMountain(int[] A) {
  int n = A.length;
  int[] inc = new int[n]; // init with 0
  int[] dec = new int[n]; 
  for (int i = 1, j = n - 2; i < n; ++i, --j) {
    if (A[i - 1] < A[i]) inc[i] = inc[i - 1] + 1;
    if (A[j] > A[j + 1]) dec[j] = dec[j + 1] + 1;
    // otherwise, keep it 0
  }
  // for each possible peak
  int maxLen = 0;
  for (int i = 1; i < n - 1; ++i) {
    if (inc[i] > 0 && dec[i] > 0) {
      maxLen = Math.max(maxLen, inc[i] + dec[i] + 1);
    }
  }
  return maxLen;
}

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