Longest Mountain in Array — LC 845 Two Pointer Peak Expansion

Problem Statement#

A mountain is a subarray that is strictly increasing then strictly decreasing with at least 3 elements. Return the length of the longest such subarray, or 0 if none exists.

Constraints:

• 1 less than or equal to arr.length less than or equal to 10 to the 4
• 0 less than or equal to arr[i] less than or equal to 10 to the 4

Input:  arr = [2, 1, 4, 7, 3, 2, 5]
Output: 5

Input:  arr = [2, 2, 2]
Output: 0

Why This Problem Matters#

LeetCode 845 — Longest Mountain in Array is a Google, Amazon, and Bloomberg favorite because it tests pointer-state discipline. The textbook two-pointer template assumes monotonic windows, but a mountain has two regimes: ascending, then descending. Mishandling the transition is the most common bug, and interviewers grade specifically for that.

There are two clean approaches: a two-pass slope count (compute increasing run lengths from left and decreasing run lengths from right, combine at peaks) and a single-pass two-pointer expansion (find each peak, walk both sides). Both are O(n) and O(1), but candidates who know both signal pattern depth.

In production, mountain detection appears in time-series spike analysis, audio peak detection, and financial-market price patterns.

The Core Insight#

A mountain has a unique peak k where arr[k - 1] less than arr[k] greater than arr[k + 1]. From a peak you can walk left while the slope is strictly increasing and walk right while the slope is strictly decreasing. The mountain length is the sum of left walk, right walk, and 1 (for the peak).

Iterate i from 1 to n - 2. Whenever i is a peak:

• Walk left from i while arr[left - 1] less than arr[left].
• Walk right from i while arr[right + 1] less than arr[right].
• Update best with right - left + 1.

The total work across all peaks is O(n) because each index participates in at most one ascending walk and one descending walk over the whole iteration (amortized).

Visual Dry Run#

Input: arr = [2, 1, 4, 7, 3, 2, 5]

Answer: 5.

Solution (Optimal)#

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

var longestMountain = function(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 left = i - 1;
            while (left > 0 && arr[left - 1] < arr[left]) left--;
            let right = i + 1;
            while (right < n - 1 && arr[right] > arr[right + 1]) right++;
            const len = right - left + 1;
            if (len > best) best = len;
            i = right;
        } else {
            i++;
        }
    }
    return best;
};

Time: O(n) — each index visited at most twice. Space: O(1) — pointers only.

Common Mistakes#

• Allowing equal neighbors. The problem requires strictly increasing and strictly decreasing.
• Counting flat plateaus as part of the mountain. A flat run breaks both regimes.
• Returning the count of peaks instead of the longest length.
• Off-by-one when computing the length: it is right - left + 1, not right - left.
• Restarting i at 1 after each peak instead of skipping to right to keep linear time.

Interview Tips#

• Define mountain precisely on the whiteboard, including the strictness requirement.
• Mention both approaches (two-pass slope count, one-pass expansion) and pick one.
• Walk through edge cases: array of length less than 3, all equal values, monotonic arrays.
• Emphasize the i = right jump as the source of amortized linear time.
• Confirm whether plateaus count as ascending — they do not.

Follow-up Questions#

• What if equal elements are allowed in the slopes? Switch to non-strict comparisons.
• Return the actual mountain bounds. Track left and right when best updates.
• Find the longest valley (descending then ascending). Mirror the comparison signs.
• Find the count of mountains, not the longest. Increment a counter at each peak.
• Stream variant: process arrivals online. Maintain current ascending and descending run lengths.

Key Takeaways#

• LeetCode 845 — Longest Mountain in Array solves in O(n) time and O(1) space.
• A mountain requires strictly increasing then strictly decreasing slopes around a unique peak.
• Each peak triggers a left walk and a right walk; total work is amortized linear.
• Always jump i to right after a peak to keep linear time.
• Plateaus do not count as ascending or descending — strict comparisons only.
• Asked at Google, Amazon, and Bloomberg as a 20-minute pointer-state warm-up.
• Two-pass slope-count and one-pass expansion are equivalent O(n) approaches.