Longest Mountain in Array - Practice Coding Problems

Longest Mountain in Array - Problem

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray which is a mountain.

Return 0 if there is no mountain subarray.

Input & Output

Example 1 — Basic Mountain

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

› Output: 5

💡 Note: The longest mountain is [1,4,7,3,2] with length 5. It goes up: 1<4<7, then down: 7>3>2.

Example 2 — No Mountain

$ Input: arr = [2,2,2]

› Output: 0

💡 Note: No mountain exists because all elements are equal. A mountain requires strictly increasing then decreasing.

Example 3 — Multiple Mountains

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

› Output: 11

💡 Note: The entire array forms one mountain: 0<1<2<3<4<5>4>3>2>1>0, length 11.

Constraints

1 ≤ arr.length ≤ 1000
0 ≤ arr[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array with potential mountain patterns

Process

Find subarrays that go strictly up then strictly down

Output

Length of longest valid mountain

Key Takeaway

🎯 Key Insight: A valid mountain must have both strictly increasing and strictly decreasing parts

Asked in

f Facebook 8 G Google 5

The key insight is that a mountain must have both strictly increasing and strictly decreasing parts. Best approach uses one pass tracking of up/down streaks. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass Solution	O(n)	O(n)	Calculate upward and downward slopes separately, then combine
One Pass Solution	O(n)	O(1)	Track mountain length in single pass using state variables
Brute Force	O(n³)	O(1)	Check every possible subarray to see if it forms a mountain

Two Pass Solution — Algorithm Steps

Calculate upward slopes from each position
Calculate downward slopes from each position
For each position, combine up and down lengths
Return maximum mountain length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Up

Find length of increasing sequence ending at each position

Calculate Down

Find length of decreasing sequence starting at each position

Combine

For each peak, combine up and down lengths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int n) {
    if (n < 3) return 0;
    
    // up[i] = length of strictly increasing sequence ending at i
    int* up = (int*)malloc(n * sizeof(int));
    // down[i] = length of strictly decreasing sequence starting at i
    int* down = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        up[i] = 1;
        down[i] = 1;
    }
    
    // Calculate upward slopes
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i-1]) {
            up[i] = up[i-1] + 1;
        }
    }
    
    // Calculate downward slopes
    for (int i = n-2; i >= 0; i--) {
        if (arr[i] > arr[i+1]) {
            down[i] = down[i+1] + 1;
        }
    }
    
    // Find maximum mountain length
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        if (up[i] > 1 && down[i] > 1) { // Must have both up and down
            int length = up[i] + down[i] - 1;
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    
    free(up);
    free(down);
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(arr, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array, each taking O(n) time

✓ Linear Growth

Space Complexity

O(n)

Two arrays to store upward and downward lengths

⚡ Linearithmic Space

67.9K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler