Longest Mountain in Array

Problem Statement

In the problem, we are provided with an array arr, and our task is to determine the length of the longest subarray that qualifies as a "mountain". A subarray is defined as a mountain if it has at least three elements, and there is a peak element such that elements before the peak strictly increase and elements after the peak strictly decrease. Specifically, the array must have this behavior in sequential order: first increasing up to a single peak element, and then decreasing continuously from this peak. If no such mountain exists, the array should return a length of 0.

Examples

Example 1

Input:

arr = [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:

arr = [2,2,2]

Output:

0

Explanation:

There is no mountain.

Constraints

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

Approach and Intuition

To tackle the problem of finding the longest mountain in the array, we can follow this strategy:

1. Initialize a variable to keep track of the maximum length of the mountain found (maxLength).
2. Traverse through the array using an index i that will attempt to identify potential peaks.
3. For each potential peak at index i, we check if it's a valid peak:
   • Make sure i is not the first or the last element in the array (since the peak needs to have elements on both sides).
   • Confirm that arr[i-1] < arr[i] > arr[i+1] to validate that it's a peak.
4. Once a peak is identified, expand from the peak in both directions:
   • Move leftwards from i - 1 and continue until the elements stop increasing.
   • Move rightwards from i + 1 and continue until the elements stop decreasing.
5. Calculate the length of the mountain for the given peak by considering the number of elements counted while expanding in both directions.
6. Compare and update the maxLength if the current mountain's length is greater than previously recorded lengths.
7. After completing the scan of the array, return maxLength as the length of the longest mountain.

Considerations based on constraints:

• If the array has less than 3 elements, it's impossible to form a mountain, so we return 0 immediately.
• Since each peak check involves expanding to both the left and right, the worst case computational complexity is O(n), where n is the number of elements in the array. This is efficient given the constraints provided.

Solutions

class Solution {
    public int maxMountainLength(int[] arr) {
        int arrayLength = arr.length;
        int maxLen = 0, startPoint = 0;
        while (startPoint < arrayLength) {
            int peak = startPoint;
            if (peak + 1 < arrayLength && arr[peak] < arr[peak + 1]) {
                while (peak + 1 < arrayLength && arr[peak] < arr[peak + 1]) peak++;
                if (peak + 1 < arrayLength && arr[peak] > arr[peak + 1]) {
                    while (peak + 1 < arrayLength && arr[peak] > arr[peak + 1]) peak++;
                    maxLen = Math.max(maxLen, peak - startPoint + 1);
                }
            }
            startPoint = Math.max(peak, startPoint + 1);
        }
        return maxLen;
    }
}