Problem Description

Given an array of integers arr, a mountain is defined as a sequence of at least three elements that strictly increases to a single peak and then strictly decreases. More formally, a subarray arr[i..j] is a mountain if:

• i + 1 < j (the mountain is at least length 3)
• There exists some k with i < k < j such that:
• arr[i] < arr[i+1] < ... < arr[k]
• arr[k] > arr[k+1] > ... > arr[j]

Constraints:

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

Thought Process

To solve this problem, we need to identify subarrays that form a valid "mountain" shape. The brute-force approach would be to check every possible subarray of length at least 3, verify if it increases to a peak and then decreases. However, this is inefficient for large arrays.

Instead, we can optimize by focusing on the peak of each potential mountain. If we can efficiently find peaks (where arr[i-1] < arr[i] > arr[i+1]), we can then expand outwards from each peak to determine the full extent of the mountain. This allows us to avoid redundant checks and unnecessary computations.

The key insight is that a valid mountain must have a strictly increasing sequence before the peak and a strictly decreasing sequence after. By scanning for peaks and expanding left and right, we can efficiently find and track the longest mountain.

Solution Approach

Let's break down the efficient solution step-by-step:

1. Iterate through the array: For each index i from 1 to len(arr) - 2, check if arr[i] is a peak (i.e., arr[i-1] < arr[i] > arr[i+1]).
2. Expand to the left: From the peak at i, move left as long as the sequence is strictly increasing (arr[left - 1] < arr[left]).
3. Expand to the right: From the peak at i, move right as long as the sequence is strictly decreasing (arr[right] > arr[right + 1]).
4. Calculate mountain length: The length of the mountain is right - left + 1.
5. Track the maximum: Keep updating the maximum length found so far.
6. Skip processed elements: After processing a mountain, move i to right to avoid redundant checks.

This approach ensures we only process each mountain once and never revisit elements unnecessarily, leading to efficient performance.

Example Walkthrough

Consider the input arr = [2, 1, 4, 7, 3, 2, 5].

• We start at index 1: arr[0]=2, arr[1]=1, arr[2]=4 – not a peak.
• Index 2: arr[1]=1, arr[2]=4, arr[3]=7 – not a peak.
• Index 3: arr[2]=4, arr[3]=7, arr[4]=3 – peak found (4 < 7 > 3).
• Expand left: arr[1]=1 < arr[2]=4, so left = 1.
• Expand right: arr[4]=3 > arr[5]=2, so right = 5.
• Mountain is arr[1..5] = [1, 4, 7, 3, 2], length = 5.
• Continue from index 5: arr[4]=3, arr[5]=2, arr[6]=5 – not a peak.
• No more peaks. So, the longest mountain has length 5.

The function returns 5.

Code Implementation

class Solution:
    def longestMountain(self, arr):
        n = len(arr)
        max_len = 0
        i = 1
        while i < n - 1:
            if arr[i-1] < arr[i] > arr[i+1]:
                left = i - 1
                right = i + 1
                while left > 0 and arr[left-1] < arr[left]:
                    left -= 1
                while right < n - 1 and arr[right] > arr[right+1]:
                    right += 1
                max_len = max(max_len, right - left + 1)
                i = right
            else:
                i += 1
        return max_len
      

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int maxLen = 0, i = 1;
        while (i < n - 1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                int left = i - 1, right = i + 1;
                while (left > 0 && arr[left-1] < arr[left]) --left;
                while (right < n - 1 && arr[right] > arr[right+1]) ++right;
                maxLen = max(maxLen, right - left + 1);
                i = right;
            } else {
                ++i;
            }
        }
        return maxLen;
    }
};
      

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int maxLen = 0, i = 1;
        while (i < n - 1) {
            if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
                int left = i - 1, right = i + 1;
                while (left > 0 && arr[left-1] < arr[left]) left--;
                while (right < n - 1 && arr[right] > arr[right+1]) right++;
                maxLen = Math.max(maxLen, right - left + 1);
                i = right;
            } else {
                i++;
            }
        }
        return maxLen;
    }
}
      

var longestMountain = function(arr) {
    let n = arr.length;
    let maxLen = 0, i = 1;
    while (i < n - 1) {
        if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) {
            let left = i - 1, right = i + 1;
            while (left > 0 && arr[left-1] < arr[left]) left--;
            while (right < n - 1 && arr[right] > arr[right+1]) right++;
            maxLen = Math.max(maxLen, right - left + 1);
            i = right;
        } else {
            i++;
        }
    }
    return maxLen;
};
      

Time and Space Complexity

Brute-force approach: For every possible subarray of length at least 3, we check if it forms a mountain. This would take O(N³) time, which is too slow for large arrays.

Optimized approach: The peak expansion method only processes each element at most twice (once going left, once going right), so the total time complexity is O(N). Space complexity is O(1) since we only use a few variables for tracking indices and maximum length.

Summary

The "Longest Mountain in Array" problem is efficiently solved by focusing on the peaks of potential mountains and expanding outwards to determine their full extent. By checking for strict increases and decreases, and carefully managing indices, we avoid unnecessary work and achieve a linear-time solution. The approach is elegant because it leverages the natural structure of a mountain, ensuring each mountain is only processed once and the implementation remains simple and clear.