Problem Description

A mountain array is defined as an array that meets the following conditions:

1. The array has at least 3 elements (arr.length >= 3)
2. There exists a peak index i where 0 < i < arr.length - 1 such that:
   • Elements before the peak are in strictly increasing order: arr[0] < arr[1] < ... < arr[i-1] < arr[i]
   • Elements after the peak are in strictly decreasing order: arr[i] > arr[i+1] > ... > arr[arr.length-1]

Given an integer array arr, you need to find the length of the longest contiguous subarray that forms a mountain. If no such mountain subarray exists, return 0.

The solution uses dynamic programming with two arrays:

• Array f[i] tracks the length of the longest increasing sequence ending at position i
• Array g[i] tracks the length of the longest decreasing sequence starting at position i

The algorithm works in two passes:

1. Forward pass: Build array f by checking if each element is greater than the previous one. If arr[i] > arr[i-1], then f[i] = f[i-1] + 1
2. Backward pass: Build array g by checking if each element is greater than the next one. If arr[i] > arr[i+1], then g[i] = g[i+1] + 1

For each position i that can be a peak (where both f[i] > 1 and g[i] > 1), the mountain length is calculated as f[i] + g[i] - 1 (subtracting 1 because the peak is counted in both arrays). The maximum of all valid mountain lengths is returned as the answer.

Intuition

The key insight is that a mountain has three parts: an ascending slope, a peak, and a descending slope. Instead of checking every possible subarray to see if it forms a mountain (which would be inefficient), we can think about each position as a potential peak and calculate how far we can extend in both directions.

For any position to be a valid peak, we need to know:

1. How many consecutive increasing elements lead up to it (including itself)
2. How many consecutive decreasing elements follow from it (including itself)

This naturally leads to a dynamic programming approach where we precompute this information for every position. If we know the "uphill distance" and "downhill distance" for each point, we can determine if it's a valid peak and calculate the mountain length.

Consider the array [2, 1, 4, 7, 3, 2, 5]. At position 3 (value 7):

• Looking left: we have an increasing sequence 1 → 4 → 7 of length 3
• Looking right: we have a decreasing sequence 7 → 3 → 2 of length 3
• This forms a mountain of length 3 + 3 - 1 = 5 (we subtract 1 because 7 is counted twice)

The beauty of this approach is that we can compute all increasing sequences in one forward pass and all decreasing sequences in one backward pass. Then, for each position that has both an increasing sequence before it (f[i] > 1) and a decreasing sequence after it (g[i] > 1), we know it can be a peak of a mountain.

By checking during the backward pass (when we're already computing g[i]), we can simultaneously identify valid peaks and calculate mountain lengths, making the solution efficient with O(n) time complexity.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The implementation uses two auxiliary arrays and two passes through the input array to efficiently find the longest mountain:

Data Structures:

• f[i]: Stores the length of the longest increasing sequence ending at index i
• g[i]: Stores the length of the longest decreasing sequence starting at index i
• Both arrays are initialized with 1s since each element by itself has a sequence length of 1

Algorithm Steps:

1. Build the increasing sequence array (f):

   for i in range(1, n):
       if arr[i] > arr[i - 1]:
           f[i] = f[i - 1] + 1

   • Iterate forward through the array starting from index 1
   • If current element is greater than the previous one, extend the increasing sequence: f[i] = f[i-1] + 1
   • Otherwise, f[i] remains 1 (starts a new sequence)

2. Build the decreasing sequence array (g) and find the maximum mountain:

   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)

   • Iterate backward through the array starting from index n-2
   • If current element is greater than the next one, extend the decreasing sequence: g[i] = g[i+1] + 1
   • Check if position i can be a peak: it needs f[i] > 1 (has an increasing part) and g[i] > 1 (implicitly true since we just set it)
   • Calculate mountain length at this peak: f[i] + g[i] - 1
   • Update the maximum mountain length found so far

Why this works:

• A valid mountain peak at position i must have both:
  • An increasing sequence leading to it: f[i] > 1
  • A decreasing sequence starting from it: g[i] > 1
• The mountain length is f[i] + g[i] - 1 because position i is counted in both arrays
• By checking these conditions during the backward pass, we avoid a third loop and keep the time complexity at O(n)

Time Complexity: O(n) - two passes through the array Space Complexity: O(n) - for the two auxiliary arrays f and g

Example Walkthrough

Let's walk through the algorithm with the array [2, 1, 4, 7, 3, 2, 5].

Initial Setup:

• Input array: [2, 1, 4, 7, 3, 2, 5]
• Initialize f = [1, 1, 1, 1, 1, 1, 1] (length of increasing sequence ending at each position)
• Initialize g = [1, 1, 1, 1, 1, 1, 1] (length of decreasing sequence starting at each position)
• Initialize ans = 0 (maximum mountain length)

Step 1: Forward Pass (Build array f)

Starting from index 1, check if each element is greater than the previous:

• i=1: arr[1]=1 vs arr[0]=2 → 1 < 2, so f[1] stays 1
• i=2: arr[2]=4 vs arr[1]=1 → 4 > 1, so f[2] = f[1] + 1 = 2
• i=3: arr[3]=7 vs arr[2]=4 → 7 > 4, so f[3] = f[2] + 1 = 3
• i=4: arr[4]=3 vs arr[3]=7 → 3 < 7, so f[4] stays 1
• i=5: arr[5]=2 vs arr[4]=3 → 2 < 3, so f[5] stays 1
• i=6: arr[6]=5 vs arr[5]=2 → 5 > 2, so f[6] = f[5] + 1 = 2

After forward pass: f = [1, 1, 2, 3, 1, 1, 2]

Step 2: Backward Pass (Build array g and find maximum mountain)

Starting from index 5 (n-2), check if each element is greater than the next:

• i=5: arr[5]=2 vs arr[6]=5 → 2 < 5, so g[5] stays 1

  • Check peak: f[5]=1 (not > 1), skip

• i=4: arr[4]=3 vs arr[5]=2 → 3 > 2, so g[4] = g[5] + 1 = 2

  • Check peak: f[4]=1 (not > 1), skip

• i=3: arr[3]=7 vs arr[4]=3 → 7 > 3, so g[3] = g[4] + 1 = 3

  • Check peak: f[3]=3 > 1 ✓ and g[3]=3 > 1 ✓
  • Mountain length = f[3] + g[3] - 1 = 3 + 3 - 1 = 5
  • Update ans = 5

• i=2: arr[2]=4 vs arr[3]=7 → 4 < 7, so g[2] stays 1

  • Check peak: f[2]=2 > 1 but g[2]=1 (not > 1), skip

• i=1: arr[1]=1 vs arr[2]=4 → 1 < 4, so g[1] stays 1

  • Check peak: f[1]=1 (not > 1), skip

• i=0: arr[0]=2 vs arr[1]=1 → 2 > 1, so g[0] = g[1] + 1 = 2

  • Check peak: f[0]=1 (not > 1), skip

After backward pass: g = [2, 1, 1, 3, 2, 1, 1]

Final Result:

• The maximum mountain length found is 5
• This corresponds to the subarray [1, 4, 7, 3, 2] with peak at index 3 (value 7)
• The mountain has:
  • Increasing part: 1 → 4 → 7 (length 3)
  • Decreasing part: 7 → 3 → 2 (length 3)
  • Total length: 5 elements (counting the peak once)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array.

The algorithm consists of three main parts:

• First loop: Iterates through the array once from index 1 to n-1 to populate array f, taking O(n) time
• Second loop: Iterates through the array once from index n-2 to 0 to populate array g and compute the maximum mountain length, taking O(n) time
• Array initialization: Creating two arrays of size n takes O(n) time

Total time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the input array.

The algorithm uses:

• Array f of size n to store the length of increasing sequences ending at each position: O(n) space
• Array g of size n to store the length of decreasing sequences starting at each position: O(n) space
• Variable ans and other constant variables: O(1) space

Total space complexity: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check Valid Peak Conditions

Pitfall: A common mistake is calculating the mountain length at every position without verifying that it's actually a valid peak. A valid peak must have both an increasing sequence before it AND a decreasing sequence after it.

Incorrect Implementation:

# WRONG: This calculates mountain length even for non-peaks
for i in range(n):
    max_length = max(max_length, left[i] + right[i] - 1)

Why it's wrong: This would incorrectly count sequences that are only increasing (like [1,2,3]) or only decreasing (like [3,2,1]) as mountains, when they shouldn't be.

Correct Implementation:

# Only calculate when we have both uphill and downhill
if left[i] > 1 and right[i] > 1:
    max_length = max(max_length, left[i] + right[i] - 1)

2. Off-by-One Error in Loop Boundaries

Pitfall: Using incorrect loop boundaries when building the right array, especially starting from n-1 instead of n-2.

Incorrect Implementation:

# WRONG: Starting from n-1 causes index out of bounds
for i in range(n - 1, -1, -1):
    if arr[i] > arr[i + 1]:  # Error: arr[n] doesn't exist
        right[i] = right[i + 1] + 1

Correct Implementation:

# Start from n-2 since we need to compare with i+1
for i in range(n - 2, -1, -1):
    if arr[i] > arr[i + 1]:
        right[i] = right[i + 1] + 1

3. Not Handling Edge Cases Properly

Pitfall: Not considering arrays that are too small to form mountains or arrays with duplicate values.

Example problematic cases:

• arr = [1, 2, 2, 3, 1] - Contains duplicates, which breaks the "strictly" increasing/decreasing requirement
• arr = [1, 2] - Too short to form a mountain

Solution: The algorithm naturally handles these cases:

• Duplicates: The condition arr[i] > arr[i-1] (not >=) ensures duplicates break the sequence
• Short arrays: Mountains require at least 3 elements, and our peak validation (left[i] > 1 and right[i] > 1) ensures at least 3 elements total

4. Checking Peak Validity in the Wrong Pass

Pitfall: Attempting to check for valid mountains during the forward pass when the right array hasn't been built yet.

Incorrect Implementation:

# WRONG: right array isn't built yet during forward pass
for i in range(1, n):
    if arr[i] > arr[i - 1]:
        left[i] = left[i - 1] + 1
    if left[i] > 1 and right[i] > 1:  # right[i] is still 1!
        max_length = max(max_length, left[i] + right[i] - 1)

Correct Implementation:

# Check for mountains during backward pass when both arrays are ready
for i in range(n - 2, -1, -1):
    if arr[i] > arr[i + 1]:
        right[i] = right[i + 1] + 1
        if left[i] > 1:  # Now both left[i] and right[i] are valid
            max_length = max(max_length, left[i] + right[i] - 1)