845. Longest Mountain in Array

Problem Description

You may recall that an array arr is a mountain array if and only if:

• arr.length ≥ 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Examples:

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.

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

Constraints:

• 1 ≤ arr.length ≤ 10⁴
• 0 ≤ arr[i] ≤ 10⁴

Python Solution

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 3:
            return 0
        
        longest = 0
        i = 1
        
        while i < n - 1:
            # Check if arr[i] is a peak
            if arr[i-1] < arr[i] > arr[i+1]:
                # Find left boundary
                left = i - 1
                while left > 0 and arr[left-1] < arr[left]:
                    left -= 1
                
                # Find right boundary
                right = i + 1
                while right < n - 1 and arr[right] > arr[right+1]:
                    right += 1
                
                # Update longest mountain length
                longest = max(longest, right - left + 1)
                i = right
            else:
                i += 1
        
        return longest

Implementation Notes:

• Finds peaks and expands to find mountain boundaries
• Time complexity: O(n)
• Space complexity: O(1)

Java Solution

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }
        
        int longest = 0;
        int i = 1;
        
        while (i < n - 1) {
            // Check if arr[i] is a peak
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                // Find left boundary
                int left = i - 1;
                while (left > 0 && arr[left-1] < arr[left]) {
                    left--;
                }
                
                // Find right boundary
                int right = i + 1;
                while (right < n - 1 && arr[right] > arr[right+1]) {
                    right++;
                }
                
                // Update longest mountain length
                longest = Math.max(longest, right - left + 1);
                i = right;
            } else {
                i++;
            }
        }
        
        return longest;
    }
}

C++ Solution

class Solution {
public:
    int longestMountain(vector& arr) {
        int n = arr.size();
        if (n < 3) {
            return 0;
        }
        
        int longest = 0;
        int i = 1;
        
        while (i < n - 1) {
            // Check if arr[i] is a peak
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                // Find left boundary
                int left = i - 1;
                while (left > 0 && arr[left-1] < arr[left]) {
                    left--;
                }
                
                // Find right boundary
                int right = i + 1;
                while (right < n - 1 && arr[right] > arr[right+1]) {
                    right++;
                }
                
                // Update longest mountain length
                longest = max(longest, right - left + 1);
                i = right;
            } else {
                i++;
            }
        }
        
        return longest;
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function(arr) {
    const n = arr.length;
    if (n < 3) {
        return 0;
    }
    
    let longest = 0;
    let i = 1;
    
    while (i < n - 1) {
        // Check if arr[i] is a peak
        if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
            // Find left boundary
            let left = i - 1;
            while (left > 0 && arr[left-1] < arr[left]) {
                left--;
            }
            
            // Find right boundary
            let right = i + 1;
            while (right < n - 1 && arr[right] > arr[right+1]) {
                right++;
            }
            
            // Update longest mountain length
            longest = Math.max(longest, right - left + 1);
            i = right;
        } else {
            i++;
        }
    }
    
    return longest;
};

C# Solution

public class Solution {
    public int LongestMountain(int[] arr) {
        int n = arr.Length;
        if (n < 3) {
            return 0;
        }
        
        int longest = 0;
        int i = 1;
        
        while (i < n - 1) {
            // Check if arr[i] is a peak
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                // Find left boundary
                int left = i - 1;
                while (left > 0 && arr[left-1] < arr[left]) {
                    left--;
                }
                
                // Find right boundary
                int right = i + 1;
                while (right < n - 1 && arr[right] > arr[right+1]) {
                    right++;
                }
                
                // Update longest mountain length
                longest = Math.Max(longest, right - left + 1);
                i = right;
            } else {
                i++;
            }
        }
        
        return longest;
    }
}

Implementation Notes:

• Uses two-pointer technique to find mountain boundaries
• Time complexity: O(n)
• Space complexity: O(1)