Solution For Longest Mountain In Array

Problem Statement:

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.

Solution:

The idea is to find all possible peaks and then calculate the corresponding mountain lengths. We can use two pointers to find every peak in the array. A peak is a point in the array such that its left side values are strictly increasing and its right side values are strictly decreasing. We can iterate through the array and whenever we find a peak, we can calculate the length of the mountain as the sum of its left and right side lengths (the left and right sides of the peak).

Algorithm:

Initialize two pointers, left and right, to index 1 and move them to find the first peak of the mountain.
If there is no peak, return 0.
Otherwise, initialize the variable length to 3 (the length of the peak).
Move the left pointer to the left to find the left side of the mountain (which should be strictly increasing).
Increase the length of the mountain by 1 for each number we encounter while moving the left pointer.
Move the right pointer to find the right side of the mountain (which should be strictly decreasing).
Increase the length of the mountain by 1 for each number we encounter while moving the right pointer.
If both left and right pointers reach the end of the array or have not moved, return the length of the mountain. Otherwise, repeat steps 2-6 starting from the right pointer’s current position.

Pseudo code:

int longestMountain(vector& A) {
int n = A.size();
int ans = 0, left, right;
for (int i = 1; i < n-1;) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
left = i-1;
right = i+1;
while (left > 0 && A[left] > A[left-1]) {
left–;
}
while (right < n-1 && A[right] > A[right+1]) {
right++;
}
ans = max(ans, right-left+1);
i = right;
} else {
i++;
}
}
return ans;
}

Time Complexity: O(n) – we iterate through the array at most twice.

Space Complexity: O(1) – we use only constant space for variables.

Step by Step Implementation For Longest Mountain In Array

public int longestMountain(int[] A) {
        int N = A.length, res = 0;
        int[] up = new int[N], down = new int[N];
        for (int i = N - 2; i >= 0; --i)
            if (A[i] > A[i + 1]) down[i] = down[i + 1] + 1;
        for (int i = 0; i < N; ++i) {
            if (i > 0 && A[i] > A[i - 1]) up[i] = up[i - 1] + 1;
            if (up[i] > 0 && down[i] > 0) res = Math.max(res, up[i] + down[i] + 1);
        }
        return res;
    }

def longestMountain(A):
        # keep track of longest mountain length
        longest = 0
        # iterate through array
        for i in range(1, len(A)-1):
                # check if current index is the start of a mountain
                if A[i] > A[i-1] and A[i] > A[i+1]:
                        # keep track of mountain length
                        mountain_length = 1
                        # check left side of mountain
                        left = i-1
                        while left > 0 and A[left] < A[left-1]:
                                mountain_length += 1
                                left -= 1
                        # check right side of mountain
                        right = i+1
                        while right < len(A)-1 and A[right] < A[right+1]:
                                mountain_length += 1
                                right += 1
                        # update longest mountain length if necessary
                        longest = max(longest, mountain_length)
        return longest

var longestMountain = function(A) {
    let max = 0;
    let i = 1;
    while (i < A.length - 1) {
        let up = 0;
        let down = 0;
        // check if there is an upward trend
        if (A[i] > A[i-1]) {
            up++;
            // check for a downward trend
            while (i+1 < A.length && A[i] > A[i+1]) {
                down++;
                i++;
            }
            // check if this is a valid mountain
            if (down > 0 && A[i] < A[i-1]) {
                max = Math.max(max, up+down+1);
            }
        }
        i++;
    }
    return max;
};

class Solution {
public:
    int longestMountain(vector& A) {
        int N = A.size(), res = 0, up = 0, down = 0;
        for (int i = 1; i < N; ++i) {
            if (down && A[i - 1] < A[i] || A[i - 1] == A[i]) up = down = 0;
            up += A[i - 1] < A[i];
            down += A[i - 1] > A[i];
            if (up && down) res = max(res, up + down + 1);
        }
        return res;
    }
};

public int LongestMountain(int[] A) {
        // edge case
        if (A.Length < 3) return 0;
        
        int longest = 0;
        int up = 0;
        int down = 0;
        
        for (int i = 1; i < A.Length; i++) {
            // reset if we hit a plateau
            if (down > 0 && A[i - 1] < A[i] || A[i - 1] == A[i]) {
                up = 0;
                down = 0;
            }
            
            // we are going up!
            if (A[i - 1] < A[i]) {
                up++;
            }
            
            // we are going down!
            if (A[i - 1] > A[i]) {
                down++;
            }
            
            // if we hit a peak
            if (up > 0 && down > 0) {
                longest = Math.Max(longest, up + down + 1);
            }
        }
        
        return longest;
    }