Skip to main content
CodePeet

Longest Mountain in Array

Try it yourself
MediumProblemExternal link

Description

A list of numbers is a mountain when:

  • it has at least 3 numbers, and
  • it strictly rises to a single peak and then strictly falls: arr[0] < arr[1] < … < arr[p] and arr[p] > arr[p+1] > … > arr[last], where the peak p is neither the first nor the last number.

Given an integer array arr, return the length of the longest contiguous stretch of arr that is a mountain, or 0 if there is none.

Two details matter:

  • "Strictly" means a flat step (two equal neighbours) is not allowed anywhere in a mountain.
  • A mountain needs both a climb and a fall. A stretch that only rises, or only falls, does not count.

Examples

Example 1

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

Output: 5

Explanation: 1 3 5 4 2 (positions 0 to 4) rises 1 → 3 → 5 and then falls 5 → 4 → 2, a mountain of length 5. It cannot continue, because 2 → 6 rises again and a mountain has only one peak. That low 2 then starts a second mountain, 2 6 3 (positions 4 to 6), so the two mountains share the 2. The second one ends at the flat step 3 → 3, with length 3.

Example 2

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

Output: 0

Explanation: It rises to 4 and falls from 4, but the top is flat (4 → 4). A mountain needs a single strict peak, so neither 0 2 4 4 2 0 nor any shorter stretch of it counts.

Example 3

Input: arr = [5, 4, 3]

Output: 0

Explanation: The numbers only fall. A mountain needs a climb before its fall.

Constraints

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

Editorial

Brute Force

Intuition

Check every stretch of at least 3 numbers, and keep the length of the longest one that is a mountain.

Checking one stretch is a short walk. From its first number, step forward while the numbers rise. If no rise happened at all, or the climb reached the last number with no room left to fall, it is not a mountain. Otherwise keep stepping forward while the numbers fall. It is a mountain exactly when that fall reaches the stretch's last number.

Step-by-Step Explanation

We trace Example 2, [0, 2, 4, 4, 2, 0]. The shaded window is the stretch being checked.

Step 1: Check every stretch of at least 3 numbers of [0 2 4 4 2 0]. The best starts at 0.

Step 2: Positions 0–2, [0 2 4]: it only climbs and never falls → not a mountain.

Step 3: Positions 0–3, [0 2 4 4]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 4: Positions 0–4, [0 2 4 4 2]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 5: Positions 0–5, [0 2 4 4 2 0]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 6: Positions 1–3, [2 4 4]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 7: Positions 1–4, [2 4 4 2]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 8: Positions 1–5, [2 4 4 2 0]: it climbs to 4 and then goes flat (4 → 4), and a mountain allows no flat step → not a mountain.

Step 9: Positions 2–4, [4 4 2]: it starts by staying flat (4 → 4), so there is no climb → not a mountain.

Step 10: Positions 2–5, [4 4 2 0]: it starts by staying flat (4 → 4), so there is no climb → not a mountain.

Step 11: Positions 3–5, [4 2 0]: it starts by falling (4 → 2), so there is no climb → not a mountain.

Step 12: All 10 stretches are checked and none is a mountain. Return 0.

Brute Force — Checking Every Stretch — The shaded window is the stretch being checked; green marks its peak when it is a mountain, amber marks the step where it stops being one.

Algorithm

  1. Set best = 0.
  2. For every start i and every end j ≥ i + 2:
    • Walk from i while the next number is larger. Stop if there was no rise, or if the walk reached j.
    • Keep walking while the next number is smaller.
    • If the walk ends exactly at j, the stretch is a mountain: best = max(best, j − i + 1).
  3. Return best.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
    bool isMountain(const vector<int>& arr, int i, int j) {
        int k = i;
        while (k < j && arr[k] < arr[k + 1]) k++;  // climb as far as possible
        if (k == i || k == j) return false;        // no climb at all, or no room left to come down
        while (k < j && arr[k] > arr[k + 1]) k++;  // then fall
        return k == j;                             // a mountain falls all the way to its last number
    }

public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size(), best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 2; j < n; j++)  // a mountain needs at least 3 numbers
                if (isMountain(arr, i, j)) best = max(best, j - i + 1);
        return best;
    }
};
class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        n = len(arr)
        best = 0
        for i in range(n):
            for j in range(i + 2, n):  # a mountain needs at least 3 numbers
                if self.is_mountain(arr, i, j):
                    best = max(best, j - i + 1)
        return best

    def is_mountain(self, arr: list[int], i: int, j: int) -> bool:
        k = i
        while k < j and arr[k] < arr[k + 1]:  # climb as far as possible
            k += 1
        if k == i or k == j:  # no climb at all, or no room left to come down
            return False
        while k < j and arr[k] > arr[k + 1]:  # then fall
            k += 1
        return k == j  # a mountain falls all the way to its last number
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length, best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 2; j < n; j++)  // a mountain needs at least 3 numbers
                if (isMountain(arr, i, j)) best = Math.max(best, j - i + 1);
        return best;
    }

    private boolean isMountain(int[] arr, int i, int j) {
        int k = i;
        while (k < j && arr[k] < arr[k + 1]) k++;  // climb as far as possible
        if (k == i || k == j) return false;        // no climb at all, or no room left to come down
        while (k < j && arr[k] > arr[k + 1]) k++;  // then fall
        return k == j;                             // a mountain falls all the way to its last number
    }
}

Complexity Analysis

Let n be the length of arr.

Time Complexity: O(n³). There are about n²/2 stretches, and checking one can walk all of it.

Space Complexity: O(1).

Why This Approach Is Not Efficient

The work grows with the cube of the length: doubling the array makes it about 8 times slower. Measured on a single long mountain, this takes 2.6 s in Python for 1,000 numbers and 2.2 s in C++ for 4,000. At the full 10^4 numbers that is roughly 45 minutes in Python and over half a minute in C++.

The waste is that neighbouring stretches share almost all of their climbs and falls, and every check walks them again from scratch.

A better way to look at it: a mountain is fixed by its peak. For a given peak, the longest mountain simply takes the whole climb that ends at the peak and the whole fall that starts there. Extending either one as far as it goes keeps it a mountain and only makes it longer. So instead of checking stretches, count, for every position, how long the climb into it is and how long the fall out of it is.

Better Approach - Climb and Fall Tables

Intuition

Make two tables of the same length as arr:

  • up[i] = how many rising steps end at position i. It is up[i−1] + 1 when arr[i−1] < arr[i], and 0 otherwise. Fill it from left to right.
  • down[i] = how many falling steps start at position i. It is down[i+1] + 1 when arr[i] > arr[i+1], and 0 otherwise. Fill it from right to left.
Example 1 as bars, 1 3 5 4 2 6 3 3, with each step between neighbours marked up, down or flat. The first five bars form a mountain with peak 5: 2 + 2 + 1 = 5. The bars 2 6 3 form a second mountain with peak 6: 1 + 1 + 1 = 3. The low 2 belongs to both, and the flat step 3 to 3 at the end stops the second.

A position is a peak exactly when it has both, up[i] > 0 and down[i] > 0. Its longest mountain covers up[i] steps of climb and down[i] steps of fall. A stretch of numbers always holds one more number than it has steps, so its length is:

length = up[i] + down[i] + 1

A flat step sets both counts to 0 on either side of it, which is exactly why it breaks a mountain.

Step-by-Step Explanation

We trace Example 1, [1, 3, 5, 4, 2, 6, 3, 3]. The second row fills in up from the left; the third row fills in down from the right.

Step 1: Set up two rows: up (rising steps ending at each position) and down (falling steps starting there). up[0] = 0 and down[7] = 0.

Step 2: up[1] = 1 (1 → 3 is a rise).

Step 3: up[2] = 2 (3 → 5 is a rise).

Step 4: up[3] = 0 (5 → 4 is a fall).

Step 5: up[4] = 0 (4 → 2 is a fall).

Step 6: up[5] = 1 (2 → 6 is a rise).

Step 7: up[6] = 0 (6 → 3 is a fall).

Step 8: up[7] = 0 (3 → 3 is flat).

Step 9: down[6] = 0 (3 → 3 is flat).

Step 10: down[5] = 1 (6 → 3 is a fall).

Step 11: down[4] = 0 (2 → 6 is a rise).

Step 12: down[3] = 1 (4 → 2 is a fall).

Step 13: down[2] = 2 (5 → 4 is a fall).

Step 14: down[1] = 0 (3 → 5 is a rise).

Step 15: down[0] = 0 (1 → 3 is a rise).

Step 16: Position 2 is a peak (up 2, down 2): a mountain of 2 + 2 + 1 = 5 — the best so far.

Step 17: Position 5 is a peak (up 1, down 1): a mountain of 1 + 1 + 1 = 3.

Step 18: Only positions 2 and 5 are peaks. Return 5.

Climb and Fall Tables — Row 1: the array. Row 2: rising steps ending at each position. Row 3: falling steps starting there. A peak has both, and its mountain is climb + fall + 1.

Algorithm

  1. Create up and down, both all 0, of length n.
  2. For i from 1 to n − 1: if arr[i−1] < arr[i], set up[i] = up[i−1] + 1.
  3. For i from n − 2 down to 0: if arr[i] > arr[i+1], set down[i] = down[i+1] + 1.
  4. For every i with up[i] > 0 and down[i] > 0, update best = max(best, up[i] + down[i] + 1).
  5. Return best.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        vector<int> up(n, 0);    // up[i]: rising steps that end at i
        vector<int> down(n, 0);  // down[i]: falling steps that start at i
        for (int i = 1; i < n; i++)
            if (arr[i - 1] < arr[i]) up[i] = up[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--)
            if (arr[i] > arr[i + 1]) down[i] = down[i + 1] + 1;
        int best = 0;
        for (int i = 0; i < n; i++)
            if (up[i] > 0 && down[i] > 0)  // i is a peak: it has both a climb and a fall
                best = max(best, up[i] + down[i] + 1);
        return best;
    }
};
class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        n = len(arr)
        up = [0] * n    # up[i]: rising steps that end at i
        down = [0] * n  # down[i]: falling steps that start at i
        for i in range(1, n):
            if arr[i - 1] < arr[i]:
                up[i] = up[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                down[i] = down[i + 1] + 1
        best = 0
        for i in range(n):
            if up[i] > 0 and down[i] > 0:  # i is a peak: it has both a climb and a fall
                best = max(best, up[i] + down[i] + 1)
        return best
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int[] up = new int[n];    // up[i]: rising steps that end at i
        int[] down = new int[n];  // down[i]: falling steps that start at i
        for (int i = 1; i < n; i++)
            if (arr[i - 1] < arr[i]) up[i] = up[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--)
            if (arr[i] > arr[i + 1]) down[i] = down[i + 1] + 1;
        int best = 0;
        for (int i = 0; i < n; i++)
            if (up[i] > 0 && down[i] > 0)  // i is a peak: it has both a climb and a fall
                best = Math.max(best, up[i] + down[i] + 1);
        return best;
    }
}

Complexity Analysis

Let n be the length of arr.

Time Complexity: O(n). Three passes over the array: one for each table, one for the peaks. At full size this takes a few milliseconds.

Space Complexity: O(n) for the two tables.

Why This Approach Is Not Efficient

This is already linear, but it walks the array three times and keeps two extra arrays of n numbers. The problem's follow-up asks for one pass and O(1) extra space.

Look at what the tables are really used for. At any moment, only the climb and fall of the mountain currently being walked matter. Everything to the left is finished, and its best length has already been recorded. So two running counters are enough.

Optimal Approach - One Pass With Two Counters

Intuition

Walk from left to right with two counters: up, the rising steps of the current mountain, and down, its falling steps. Each step between neighbours does one of four things:

  • Flat (arr[i−1] == arr[i]): no mountain can continue through it. Reset both counts to 0.
  • Rise after a fall (down > 0 and a rise): the old mountain is finished. The valley between them starts a new one, so reset both counts, then count this rise.
  • Rise: up += 1.
  • Fall: down += 1.

Whenever up > 0 and down > 0, the stretch being walked is a mountain of length up + down + 1, so update the best.

The "rise after a fall" rule is what lets two mountains share a valley, as in Example 1. The low 2 is the last number of one mountain and the first of the next.

Step-by-Step Explanation

We trace Example 1 again. The row underneath marks each step as it is read; the window is the mountain currently being walked.

Step 1: Start with up = 0, down = 0 and best = 0.

Step 2: 1 → 3: up = 1.

Step 3: 3 → 5: up = 2.

Step 4: 5 → 4: down = 1; mountain of 4 — best so far.

Step 5: 4 → 2: down = 2; mountain of 5 — best so far.

Step 6: 2 → 6: rise after a fall — start a new mountain, up = 1.

Step 7: 6 → 3: down = 1; mountain of 3.

Step 8: 3 → 3: flat — reset both counts to 0.

Step 9: The walk is over. Return 5.

One Pass With Two Counters — The row underneath marks each step as a rise, a fall or flat; the window is the mountain currently being walked.

Algorithm

  1. Set best = up = down = 0.
  2. For i from 1 to n − 1:
    • If arr[i−1] == arr[i], or down > 0 and arr[i−1] < arr[i]: set up = down = 0.
    • If arr[i−1] < arr[i]: up += 1. Else if arr[i−1] > arr[i]: down += 1.
    • If up > 0 and down > 0: best = max(best, up + down + 1).
  3. Return best.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int best = 0, up = 0, down = 0;  // up, down: rising and falling steps of the mountain being walked
        for (int i = 1; i < (int)arr.size(); i++) {
            // A flat step breaks any mountain, and a rise after a fall starts a new one.
            if (arr[i - 1] == arr[i] || (down > 0 && arr[i - 1] < arr[i])) up = down = 0;
            if (arr[i - 1] < arr[i]) up++;
            else if (arr[i - 1] > arr[i]) down++;
            if (up > 0 && down > 0) best = max(best, up + down + 1);
        }
        return best;
    }
};
class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        best = up = down = 0  # up, down: rising and falling steps of the mountain being walked
        for i in range(1, len(arr)):
            # A flat step breaks any mountain, and a rise after a fall starts a new one.
            if arr[i - 1] == arr[i] or (down > 0 and arr[i - 1] < arr[i]):
                up = down = 0
            if arr[i - 1] < arr[i]:
                up += 1
            elif arr[i - 1] > arr[i]:
                down += 1
            if up > 0 and down > 0:
                best = max(best, up + down + 1)
        return best
class Solution {
    public int longestMountain(int[] arr) {
        int best = 0, up = 0, down = 0;  // up, down: rising and falling steps of the mountain being walked
        for (int i = 1; i < arr.length; i++) {
            // A flat step breaks any mountain, and a rise after a fall starts a new one.
            if (arr[i - 1] == arr[i] || (down > 0 && arr[i - 1] < arr[i])) up = down = 0;
            if (arr[i - 1] < arr[i]) up++;
            else if (arr[i - 1] > arr[i]) down++;
            if (up > 0 && down > 0) best = Math.max(best, up + down + 1);
        }
        return best;
    }
}

Complexity Analysis

Let n be the length of arr.

Time Complexity: O(n). A single pass, with constant work per step.

Space Complexity: O(1). Three integers: up, down and best.

This is the least any solution can do. Every number has to be read at least once, because changing any one of them could create or break a mountain.