Longest Mountain in Array

medium array two pointers dp enumeration

Problem

Return the length of the longest subarray that strictly increases then strictly decreases (a "mountain"). A mountain must have length ≥ 3.

Inputarr = [2,1,4,7,3,2,5]

Output5

[1,4,7,3,2] climbs to peak 7 then descends — length 5.

arr (comma-separated)

def longestMountain(arr):
    n = len(arr)
    best = 0
    i = 1
    while i < n - 1:
        if arr[i - 1] < arr[i] > arr[i + 1]:
            l = i - 1
            while l > 0 and arr[l - 1] < arr[l]: l -= 1
            r = i + 1
            while r < n - 1 and arr[r] > arr[r + 1]: r += 1
            best = max(best, r - l + 1)
            i = r
        i += 1
    return best

function longestMountain(arr) {
  const n = arr.length;
  let best = 0, i = 1;
  while (i < n - 1) {
    if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
      let l = i - 1;
      while (l > 0 && arr[l - 1] < arr[l]) l--;
      let r = i + 1;
      while (r < n - 1 && arr[r] > arr[r + 1]) r++;
      best = Math.max(best, r - l + 1);
      i = r;
    }
    i++;
  }
  return best;
}

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

int longestMountain(vector<int>& arr) {
    int n = (int)arr.size(), best = 0, i = 1;
    while (i < n - 1) {
        if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
            int l = i - 1;
            while (l > 0 && arr[l - 1] < arr[l]) l--;
            int r = i + 1;
            while (r < n - 1 && arr[r] > arr[r + 1]) r++;
            best = max(best, r - l + 1);
            i = r;
        }
        i++;
    }
    return best;
}

Explanation

A "mountain" is a stretch that strictly climbs then strictly falls, with a single highest point in the middle. The smart move is to find each peak first, then expand outward from it, instead of testing every possible subarray.

Walk i through the array. A spot is a peak when arr[i-1] < arr[i] > arr[i+1] — taller than both neighbors. Once a peak is found, slide a left pointer l downhill to the left while the values keep rising toward the peak, and slide a right pointer r downhill to the right while the values keep falling.

The mountain length is r - l + 1, and we keep the maximum in best. We then set i = r so the scan resumes from the foot of this mountain rather than re-walking ground we already covered.

Example: arr = [2,1,4,7,3,2,5]. The peak is 7 at index 3. Expanding left reaches index 1 (value 1) and right reaches index 5 (value 2), giving [1,4,7,3,2] of length 5.

Each element is visited a constant number of times overall, so the whole scan runs in O(n) time.

Time: O(n) Space: O(1)