Valid Mountain Array

easy array two pointers

Problem

Given an array of integers arr, return true if and only if it is a valid mountain array. The array is a mountain if it has at least 3 elements, there exists an index i (with 0 < i < arr.length − 1) such that arr[0] < arr[1] < … < arr[i], and arr[i] > arr[i+1] > … > arr[last]. Both the climb and the descent must be strict, and there must be exactly one peak.

Inputarr = [0, 3, 2, 1]

Outputtrue

It rises 0 < 3 to the peak at index 1, then falls 3 > 2 > 1. The peak is not at either end.

arr (comma-separated)

def valid_mountain_array(arr):
    n = len(arr)
    i = 0
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1
    if i == 0 or i == n - 1:
        return False
    while i + 1 < n and arr[i] > arr[i + 1]:
        i += 1
    return i == n - 1

function validMountainArray(arr) {
  const n = arr.length;
  let 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;
}

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length, 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;
    }
}

bool validMountainArray(vector<int>& arr) {
    int n = (int)arr.size(), 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;
}

Explanation

A mountain must strictly climb up to one peak and then strictly fall all the way to the end. This solution checks that shape with a single walk and no extra memory.

First, starting at i = 0, we keep stepping forward while each value is bigger than the one before (arr[i] < arr[i+1]). When this loop stops, i sits at the top of the climb.

Then a quick guard: if i == 0 the array never went up, and if i == n - 1 it never came down. Either case means there is no real peak, so we return false.

Next we keep stepping forward while values strictly decrease. If we reach the last index (i == n - 1), the descent was clean and the whole thing is a valid mountain.

Example: [0, 3, 2, 1]. We climb 0<3 and stop at index 1 (the peak, not an end). Then 3>2>1 walks us to the final index, so the answer is true.

Time: O(n) Space: O(1)