Left and Right Counter Algorithm to Find the Longest Mountain in Array

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.

Example 1:

Input: [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: [2,2,2]
Output: 0
Explanation: There is no mountain.
Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000
Follow up:

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

Left and Right Counter Algorithm to Compute the Longest Mountain Array

For each location in the array, we compute the number of elements on its left and right for increasing and decreasing respectively. This requires O(N) time and O(N) space. Then, we do another scan to compute the length of the mountain array and record the longest one. To qualify for a mountain array, the left and right counters need to be both non-zero.

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>& A) {
        if (A.empty()) return 0;
        vector<int> left(A.size(), 0);
        vector<int> right(A.size(), 0);
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] > A[i - 1]) {
                left[i] = left[i - 1] + 1;
            } 
        }
        for (int i = A.size() - 2; i >= 0; -- i) {
            if (A[i] > A[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int res = 0;
        for (int i = 0; i < A.size(); ++ i) {
            if (left[i] * right[i] > 0)
                res = max(res, left[i] + right[i] + 1);
        }
        return res;
    }
};

class Solution {
public:
    int longestMountain(vector<int>& A) {
        if (A.empty()) return 0;
        vector<int> left(A.size(), 0);
        vector<int> right(A.size(), 0);
        for (int i = 1; i < A.size(); ++ i) {
            if (A[i] > A[i - 1]) {
                left[i] = left[i - 1] + 1;
            } 
        }
        for (int i = A.size() - 2; i >= 0; -- i) {
            if (A[i] > A[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int res = 0;
        for (int i = 0; i < A.size(); ++ i) {
            if (left[i] * right[i] > 0)
                res = max(res, left[i] + right[i] + 1);
        }
        return res;
    }
};

The corner case is that the empty array and for arrays length up to 2, has zero longest length of mountain array.

–EOF (The Ultimate Computing & Technology Blog) —