Valid Mountain Array

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atFlipkart

Valid Mountain Array is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (one pass, climb then descend), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every peak) up.

Problem

Given an integer array arr, return true if it is a mountain and false otherwise.

An array is a mountain when it has at least three elements and there is some index p with 0 < p < arr.length - 1 such that the values strictly increase from arr[0] up to arr[p] and then strictly decrease from arr[p] down to the last element.

Examples

Example 1

Input
arr = [1, 4, 7, 5, 2]
Output
true
Why
The values rise strictly up to 7 and then fall strictly to the end.

Example 2

Input
arr = [2, 5, 5, 1]
Output
false
Why
The two 5s form a flat top, and a mountain must be strictly rising then strictly falling.

Example 3

Input
arr = [6, 4, 3]
Output
false
Why
There is no rising part: the peak would be the first element.

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 13 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 peak)O(n²)O(1)
Optimal (one pass, climb then descend)O(n)O(1)

1Brute force (try every peak)

TimeO(n²)Up to n candidate peaks, each checked against the whole array.
SpaceO(1)Only loop indices.

Try each inner index as the peak and check that everything to its left is strictly increasing and everything to its right is strictly decreasing.

  1. For every p from 1 to n - 2:
  2. Check arr[i] < arr[i + 1] for all i < p, and arr[i] > arr[i + 1] for all i >= p.
  3. If both hold, return true. If no p works, return false.
class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        for (int p = 1; p < n - 1; p++) {
            boolean ok = true;
            for (int i = 0; i < n - 1 && ok; i++) {
                if (i < p && arr[i] >= arr[i + 1]) ok = false;
                if (i >= p && arr[i] <= arr[i + 1]) ok = false;
            }
            if (ok) return true;
        }
        return false;
    }
}

2Optimal (one pass, climb then descend)

TimeO(n)The pointer only moves forward, visiting each index at most once.
SpaceO(1)One index variable.

Walk up from the start while the next value is strictly larger. The place you stop is the only possible peak; it must not be the first or the last index. Then walk down while the next value is strictly smaller. The array is a mountain exactly when this descent reaches the last index.

  1. Set i = 0; while i + 1 < n and arr[i] < arr[i + 1], increment i.
  2. If i == 0 or i == n - 1, return false.
  3. While i + 1 < n and arr[i] > arr[i + 1], increment i.
  4. Return i == n - 1.
class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        int i = 0;
        while (i + 1 < n && arr[i] < arr[i + 1]) i++;
        if (i == 0 || i == n - 1) return false;
        while (i + 1 < n && arr[i] > arr[i + 1]) i++;
        return i == n - 1;
    }
}

Edge cases to test

  • Fewer than three elements: never a mountain
  • Strictly increasing only, or strictly decreasing only: false
  • A plateau anywhere (equal neighbours): false
  • A second rise after the descent, like [1, 3, 2, 4]

Hints

Hint 1

A mountain has exactly one peak, and it cannot be the first or the last element.

Hint 2

Walk up from the left while values increase. Where do you stop?

Hint 3

From that point you must be able to walk down strictly to the very last index.

FAQ

What is the best time complexity for Valid Mountain Array?

Optimal (one pass, climb then descend) runs in O(n) time and O(1) extra space. The pointer only moves forward, visiting each index at most once.

Which pattern does Valid Mountain 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 Valid Mountain Array?

Yes. Brute force (try every peak) takes O(n²) time and O(1) space. Try each inner index as the peak and check that everything to its left is strictly increasing and everything to its right is strictly decreasing.

Which edge cases should I test for Valid Mountain Array?

Fewer than three elements: never a mountain; Strictly increasing only, or strictly decreasing only: false; A plateau anywhere (equal neighbours): false; A second rise after the descent, like [1, 3, 2, 4].