LeetCode 845 - Longest Mountain in Array

The problem asks us to find the length of the longest contiguous subarray that forms a valid mountain. A mountain is a sequence that strictly increases up to a peak, then strictly decreases afterward.

leetcodemediumarraytwo-pointersdynamic-programmingenumeration

LeetCode Problem 845

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Dynamic Programming, Enumeration

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous subarray that forms a valid mountain.

A mountain is a sequence that strictly increases up to a peak, then strictly decreases afterward. The peak cannot be the first or last element of the subarray because the mountain must contain both an uphill and a downhill portion.

More formally, for some index i:

  • Elements before i are strictly increasing
  • Elements after i are strictly decreasing
  • The subarray length must be at least 3

The input is an integer array arr, and the output is a single integer representing the length of the longest mountain subarray. If no valid mountain exists, we return 0.

The constraints are important:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4

An O(n^2) solution may still pass with careful optimization, but the follow up specifically asks for:

  • One pass
  • O(1) extra space

This strongly suggests we should aim for a linear scan.

Several edge cases are especially important:

  • Arrays shorter than 3 cannot contain a mountain.
  • Flat sections such as [2,2,2] are invalid because mountain slopes must be strictly increasing or decreasing.
  • Purely increasing arrays such as [1,2,3,4] are invalid because there is no descent.
  • Purely decreasing arrays such as [4,3,2,1] are invalid because there is no ascent.
  • Multiple mountains may overlap, so we must correctly identify each candidate peak.

Approaches

Brute Force Approach

The brute force solution checks every possible subarray and determines whether it forms a valid mountain.

For every starting index i and ending index j, we can:

  1. Extract the subarray arr[i:j+1]
  2. Verify that it strictly increases up to one peak
  3. Verify that it strictly decreases afterward
  4. Track the maximum valid length

This works because every possible subarray is examined, so no mountain can be missed.

However, checking all subarrays is expensive. There are O(n^2) subarrays, and validating each one may take O(n) time. This results in O(n^3) time complexity in the worst case.

Even with optimizations, brute force is unnecessarily slow for this problem.

Optimal Approach

The key observation is that a mountain is fully determined by its peak.

If we can identify a peak where:

  • arr[i-1] < arr[i]
  • arr[i] > arr[i+1]

then we can expand outward:

  • Move left while values are strictly increasing
  • Move right while values are strictly decreasing

The total span gives the mountain length.

An even better optimization is to scan the array once while tracking:

  • Length of current uphill sequence
  • Length of current downhill sequence

Whenever both uphill and downhill lengths are positive, we have a valid mountain.

This works because a valid mountain always consists of:

  • At least one increasing step
  • Followed by at least one decreasing step

We can compute this in linear time and constant space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Checks every subarray and validates mountain shape
Optimal O(n) O(1) Single pass tracking uphill and downhill slopes

Algorithm Walkthrough

Optimal One Pass Algorithm

  1. Initialize three variables:
  • up = 0, length of current increasing slope
  • down = 0, length of current decreasing slope
  • longest = 0, best mountain length found so far
  1. Iterate through the array starting from index 1.
  2. At each position, first determine whether the current mountain state should reset.

We reset when:

  • The sequence becomes flat, arr[i] == arr[i-1]
  • A new uphill begins after a downhill has already started

In either case:

  • Set up = 0
  • Set down = 0
  1. If arr[i] > arr[i-1], we are climbing upward.
  • Increment up
  1. If arr[i] < arr[i-1], we are descending.
  • Increment down, but only if we already had an uphill
  1. Whenever both:
  • up > 0
  • down > 0

we have a valid mountain.

The mountain length is:

up + down + 1

The extra 1 accounts for the peak element. 7. Update longest whenever a larger mountain is found. 8. After processing the array, return longest.

Why it works

The algorithm maintains the invariant that:

  • up stores the number of strictly increasing edges
  • down stores the number of strictly decreasing edges following that increase

A valid mountain exists exactly when both are positive. Since every array element is processed once, and every possible mountain must contain one increasing phase followed by one decreasing phase, the algorithm correctly identifies the longest mountain.

Python Solution

from typing import List

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)

        up = 0
        down = 0
        longest = 0

        for i in range(1, n):
            if (down > 0 and arr[i] > arr[i - 1]) or arr[i] == arr[i - 1]:
                up = 0
                down = 0

            if arr[i] > arr[i - 1]:
                up += 1
            elif arr[i] < arr[i - 1]:
                if up > 0:
                    down += 1

            if up > 0 and down > 0:
                longest = max(longest, up + down + 1)

        return longest

The implementation follows the single pass strategy directly.

The variables up and down represent the lengths of the increasing and decreasing portions of the current mountain. These are counts of edges, not elements, which is why the final mountain length is computed as up + down + 1.

The reset condition is critical. If we are already descending and encounter another increase, the previous mountain has ended and a new potential mountain begins. Flat values also invalidate mountain structure because strict inequality is required.

Whenever both up and down are positive, we know we currently have a valid mountain, so we update the answer.

Go Solution

func longestMountain(arr []int) int {
	n := len(arr)

	up := 0
	down := 0
	longest := 0

	for i := 1; i < n; i++ {

		if (down > 0 && arr[i] > arr[i-1]) || arr[i] == arr[i-1] {
			up = 0
			down = 0
		}

		if arr[i] > arr[i-1] {
			up++
		} else if arr[i] < arr[i-1] {
			if up > 0 {
				down++
			}
		}

		if up > 0 && down > 0 {
			length := up + down + 1
			if length > longest {
				longest = length
			}
		}
	}

	return longest
}

The Go implementation mirrors the Python logic closely.

Go does not require special handling for empty slices here because the loop naturally handles arrays of length less than 2. Integer overflow is not a concern because the maximum array length is only 10^4.

The implementation uses plain integer variables and constant extra memory.

Worked Examples

Example 1

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

Expected output:

5

The longest mountain is:

[1,4,7,3,2]
i arr[i-1] arr[i] up down longest Explanation
1 2 1 0 0 0 Downhill without uphill, invalid
2 1 4 1 0 0 Start climbing
3 4 7 2 0 0 Continue climbing
4 7 3 2 1 4 Begin descent
5 3 2 2 2 5 Continue descent
6 2 5 1 0 5 Reset and start new climb

Final answer:

5

Example 2

arr = [2,2,2]

Expected output:

0
i arr[i-1] arr[i] up down longest Explanation
1 2 2 0 0 0 Flat section resets
2 2 2 0 0 0 Flat section resets

No valid mountain exists.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once
Space O(1) Only a few integer variables are used

The algorithm performs a single linear scan through the array. No auxiliary arrays, stacks, or hash maps are needed, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)

        up = 0
        down = 0
        longest = 0

        for i in range(1, n):
            if (down > 0 and arr[i] > arr[i - 1]) or arr[i] == arr[i - 1]:
                up = 0
                down = 0

            if arr[i] > arr[i - 1]:
                up += 1
            elif arr[i] < arr[i - 1]:
                if up > 0:
                    down += 1

            if up > 0 and down > 0:
                longest = max(longest, up + down + 1)

        return longest

sol = Solution()

assert sol.longestMountain([2,1,4,7,3,2,5]) == 5  # standard mountain
assert sol.longestMountain([2,2,2]) == 0  # flat array
assert sol.longestMountain([1,2,3,4,5]) == 0  # only increasing
assert sol.longestMountain([5,4,3,2,1]) == 0  # only decreasing
assert sol.longestMountain([1,3,2]) == 3  # smallest valid mountain
assert sol.longestMountain([1,2,2,3,4,3,2]) == 5  # flat section breaks mountain
assert sol.longestMountain([0,1,2,3,4,2,1,0]) == 8  # entire array is mountain
assert sol.longestMountain([1,2,1,2,3,2,1]) == 5  # multiple mountains
assert sol.longestMountain([1]) == 0  # single element
assert sol.longestMountain([1,2]) == 0  # too short
assert sol.longestMountain([1,2,3,2,1,2,3,4,3,2]) == 6  # later mountain larger
assert sol.longestMountain([0,1,0,1,0,1,0]) == 3  # repeated small mountains
Test Why
[2,1,4,7,3,2,5] Standard example with one clear mountain
[2,2,2] Flat values invalidate mountains
[1,2,3,4,5] No descending slope
[5,4,3,2,1] No ascending slope
[1,3,2] Smallest valid mountain
[1,2,2,3,4,3,2] Plateau breaks increasing sequence
[0,1,2,3,4,2,1,0] Entire array forms one mountain
[1,2,1,2,3,2,1] Multiple mountains in same array
[1] Minimum input size
[1,2] Length smaller than required mountain size
[1,2,3,2,1,2,3,4,3,2] Larger mountain appears later
[0,1,0,1,0,1,0] Repeated short mountains

Edge Cases

One important edge case is arrays containing flat sections, such as [2,2,2] or [1,2,2,1]. Mountains require strict inequality, so equal adjacent values immediately invalidate the current sequence. A common bug is accidentally treating non decreasing or non increasing sequences as valid mountains. The implementation avoids this by resetting both counters whenever equal values are encountered.

Another important edge case is a sequence that only increases or only decreases. Arrays such as [1,2,3,4] or [4,3,2,1] do not contain valid mountains because both an ascent and descent are required. The implementation correctly handles this because a mountain is only counted when both up > 0 and down > 0.

A third tricky case is overlapping mountains. Consider [1,2,1,2,3,2,1]. When the algorithm finishes descending from one mountain and encounters another increasing slope, it must reset correctly and begin tracking a new mountain. The reset condition:

if (down > 0 and arr[i] > arr[i - 1]) or arr[i] == arr[i - 1]:

ensures that a fresh mountain starts at the correct point without carrying over stale state from the previous descent.