Longest Mountain In Array - Leetcode Solution

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<int>& 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.

1