Longest Mountain in Array

Medium Arrays & Hashing Two Pointer Original on LeetCode

Longest Mountain in Array is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (one pass, jump to the end of each climb), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every start) up.

Problem

A contiguous subarray is a mountain if it has at least 3 elements and there is a peak position inside it (not at either end) such that the values strictly increase up to the peak and strictly decrease after it.

Given an integer array arr, return the length of the longest subarray that is a mountain, or 0 if no mountain exists.

Examples

Example 1

Input
arr = [4, 1, 3, 6, 6, 2, 5, 8, 7, 3, 1]
Output
6
Why
The run [2, 5, 8, 7, 3, 1] climbs to 8 and then falls; [1, 3, 6] is not a mountain because the next value 6 is not lower.

Example 2

Input
arr = [9, 7, 5, 5, 3]
Output
0
Why
The array never goes up, so there is no peak and no mountain.

Example 3

Input
arr = [0, 4, 1, 2, 5, 3]
Output
4
Why
[0, 4, 1] has length 3, but [1, 2, 5, 3] has length 4. The 1 is shared as the end of one and the start of the other.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every start)O(n²)O(1)
Optimal (one pass, jump to the end of each climb)O(n)O(1)

1Brute force (try every start)

TimeO(n²)Each of the n starts can walk up to n steps, e.g. on a long increasing array.
SpaceO(1)Only indices.

For every index taken as the left foot of a mountain, walk up while values strictly rise, then down while they strictly fall. If both phases took at least one step, that is a mountain; keep the longest.

  1. For each start i: set j = i.
  2. While arr[j] < arr[j + 1], move j right. If j == i, no climb: skip.
  3. Remember the peak, then while arr[j] > arr[j + 1], move j right. If j is still the peak, no descent: skip.
  4. Update the answer with j - i + 1.
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length, best = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j + 1 < n && arr[j] < arr[j + 1]) j++;
            if (j == i) continue;
            int peak = j;
            while (j + 1 < n && arr[j] > arr[j + 1]) j++;
            if (j == peak) continue;
            best = Math.max(best, j - i + 1);
        }
        return best;
    }
}

2Optimal (one pass, jump to the end of each climb)

TimeO(n)`base` only moves forward and `end` never goes back past it, so each index is scanned O(1) times.
SpaceO(1)Two indices and the best length.

Same walk as the brute force, but never restart inside a run you have already scanned. After walking from base to end, the next mountain can start no earlier than end (a valley can be shared), so set base = max(end, base + 1). Every index is visited a constant number of times.

  1. Set base = 0.
  2. From end = base, climb while values rise. If it climbed, descend while values fall; if it also descended, record end - base + 1.
  3. Set base = max(end, base + 1) and repeat until base reaches n.
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length, best = 0, base = 0;
        while (base < n) {
            int end = base;
            if (end + 1 < n && arr[end] < arr[end + 1]) {
                while (end + 1 < n && arr[end] < arr[end + 1]) end++;
                if (end + 1 < n && arr[end] > arr[end + 1]) {
                    while (end + 1 < n && arr[end] > arr[end + 1]) end++;
                    best = Math.max(best, end - base + 1);
                }
            }
            base = Math.max(end, base + 1);
        }
        return best;
    }
}

Edge cases to test

  • Arrays shorter than 3, which can never contain a mountain
  • Strictly increasing or strictly decreasing arrays (no peak)
  • Plateaus: equal neighbours break a mountain
  • Two mountains sharing a valley element
  • The whole array is one mountain

Hints

Hint 1

A mountain is a strictly increasing run followed immediately by a strictly decreasing run, each with at least one step.

Hint 2

From a starting point, climb as long as the values rise, then descend as long as they fall. Where should the next search start?

Hint 3

The end of one mountain can be the start of the next, so restart from the last index you reached, not after it.

FAQ

What is the best time complexity for Longest Mountain in Array?

Optimal (one pass, jump to the end of each climb) runs in O(n) time and O(1) extra space. `base` only moves forward and `end` never goes back past it, so each index is scanned O(1) times.

Which pattern does Longest Mountain in Array use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Longest Mountain in Array?

Yes. Brute force (try every start) takes O(n²) time and O(1) space. For every index taken as the left foot of a mountain, walk up while values strictly rise, then down while they strictly fall.

Which edge cases should I test for Longest Mountain in Array?

Arrays shorter than 3, which can never contain a mountain; Strictly increasing or strictly decreasing arrays (no peak); Plateaus: equal neighbours break a mountain; Two mountains sharing a valley element; The whole array is one mountain.