#845

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Mountain in Array

Find the length of the longest subarray forming a mountain pattern using state transitions and two-pointer logic efficiently.

array two pointers dynamic programming enumeration

Problem Statement

Given an integer array arr, identify the length of the longest contiguous subarray that forms a mountain. A mountain subarray is strictly increasing to a peak, then strictly decreasing, with at least three elements. Return 0 if no valid mountain exists.

For example, arr = [2,1,4,7,3,2,5] contains the longest mountain [1,4,7,3,2] with length 5. Arrays like arr = [2,2,2] contain no mountain and should return 0. Constraints include 1 <= arr.length <= 104 and 0 <= arr[i] <= 104.

Examples

Example 1

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

Output: 5

The largest mountain is [1,4,7,3,2] which has length 5.

Example 2

Input: arr = [2,2,2]

Output: 0

There is no mountain.

Constraints

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

Solution Approach

Identify Peaks with Two Pointers

Scan the array to find potential peaks where arr[i-1] < arr[i] > arr[i+1]. Use two pointers to expand left and right from each peak to compute the full mountain length. This ensures every valid mountain is counted without revisiting elements unnecessarily.

Dynamic Programming State Tracking

Maintain two state arrays or counters: one for increasing sequences from the left and one for decreasing sequences from the right. At each index, the mountain length can be calculated as left[i] + right[i] + 1. This prevents miscounting plateaus or invalid subsequences.

Update Maximum Length Efficiently

Iterate through all identified peaks and compute their mountain length using the state transitions. Keep a global maximum updated. Skip indexes that cannot form valid mountains to maintain O(N) time complexity with constant extra space.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The algorithm runs in O(N) time because each element is visited at most twice: once to compute increasing sequences and once for decreasing sequences. Space is O(1) if counters are used instead of full arrays for left/right states.

What Interviewers Usually Probe

They may ask about handling plateaus or equal consecutive elements.
Expect questions on why two pointers suffice instead of nested loops.
Be ready to explain the state transition from increasing to decreasing sequences.

Common Pitfalls or Variants

Common pitfalls

Counting plateaus as part of a mountain peak incorrectly.
Failing to require at least three elements for a valid mountain.
Overcomplicating the solution with nested loops instead of linear expansion from peaks.

Follow-up variants

Find the total number of mountains in the array rather than the longest.
Compute the longest mountain if the array can contain negative numbers.
Return the indices of the longest mountain subarray instead of its length.

FAQ

What defines a mountain in the Longest Mountain in Array problem?

A mountain is a contiguous subarray with at least three elements that strictly increases to a peak and then strictly decreases.

Can the array contain plateaus and still form a mountain?

No, equal consecutive elements break the strict increase or decrease requirement, so plateaus are invalid.

Why use two pointers for Longest Mountain in Array?

Two pointers efficiently expand left and right from peaks to calculate mountain lengths in linear time, avoiding nested loops.

What is the time complexity using state transition dynamic programming?

It is O(N) because each element is considered at most twice while computing increasing and decreasing sequences.

How do I handle arrays with no valid mountain?

Return 0 whenever no subarray meets the strict increase-then-decrease criteria with at least three elements.

terminal

Solution

Solution 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                f[i] = f[i - 1] + 1
        ans = 0
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                g[i] = g[i + 1] + 1
                if f[i] > 1:
                    ans = max(ans, f[i] + g[i] - 1)
        return ans

Solution 2

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                f[i] = f[i - 1] + 1
        ans = 0
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                g[i] = g[i + 1] + 1
                if f[i] > 1:
                    ans = max(ans, f[i] + g[i] - 1)
        return ans

Continue Practicing

#1048 longest string chain #1537 get the maximum score #42 trapping rain water