941. Valid Mountain Array

LeetCode Problem Link (opens new window)

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

Let's recall why an array is called a mountain array:

• arr.length >= 3
• There exists an index i (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]

Example 1:

• Input: arr = [2,1]
• Output: false

Example 2:

• Input: arr = [3,5,5]
• Output: false

Example 3:

• Input: arr = [0,3,2,1]
• Output: true

Thought Process

To determine if an array forms a mountain, it's essential to ensure a strict increase from the left to the peak and a strict decrease from the right to the peak.

Two pointers, left and right, can be used here, moving according to the rules illustrated in the figure:

Note that there are some crucial details, including:

• Since left and right are indices, care must be taken to avoid out-of-bound errors during movement.
• If neither left nor right moves, it indicates a strictly increasing or decreasing array, which is still not a mountain.

C++ code is as follows:

class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        if (A.size() < 3) return false;
        int left = 0;
        int right = A.size() - 1;

        // Prevent out-of-bound errors
        while (left < A.size() - 1 && A[left] < A[left + 1]) left++;

        // Prevent out-of-bound errors
        while (right > 0 && A[right] < A[right - 1]) right--;

        // If both pointers are at the same position, and neither at the start or end, it is a mountain
        if (left == right && left != 0 && right != A.size() - 1) return true;
        return false;
    }
};

For a systematic understanding of the double pointer technique, you can refer to Double Pointers Summary (opens new window).

Versions in Other Languages

Java

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) {
            return false;
        }
        int left = 0;
        int right = arr.length - 1;

        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
            left++;
        }

        while (right > 0 && arr[right] < arr[right - 1]) {
            right--;
        }

        if (left == right && left != 0 && right != arr.length - 1) {
            return true;
        }
        return false;
    }
}

Python3

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        left, right = 0, len(arr)-1
        
        while left < len(arr)-1 and arr[left+1] > arr[left]:
            left += 1
        
        while right > 0 and arr[right-1] > arr[right]:
            right -= 1
        
        return left == right and right != 0 and left != len(arr)-1

Go

func validMountainArray(arr []int) bool {
	if len(arr) < 3 {
		return false
	}

	i := 1
	flagIncrease := false
	flagDecrease := false

	for ; i < len(arr) && arr[i-1] < arr[i]; i++ {
		flagIncrease = true
	}

	for ; i < len(arr) && arr[i-1] > arr[i]; i++ {
		flagDecrease = true
	}

	return i == len(arr) && flagIncrease && flagDecrease
}

JavaScript

var validMountainArray = function(arr) {
    if (arr.length < 3) return false;
    let left = 0, right = arr.length - 1;

    while (left < arr.length && arr[left] < arr[left+1]) left++;
    while (right > 0 && arr[right-1] > arr[right]) right--;

    if (left === right && left !== 0 && right !== arr.length - 1) return true;
    return false;
};

TypeScript

function validMountainArray(arr: number[]): boolean {
    const length: number = arr.length;
    if (length < 3) return false;
    let left: number = 0,
        right: number = length - 1;
    while (left < (length - 1) && arr[left] < arr[left + 1]) {
        left++;
    }
    while (right > 0 && arr[right] < arr[right - 1]) {
        right--;
    }
    if (left === right && left !== 0 && right !== length - 1)
        return true;
    return false;
};

C#

public class Solution {
    public bool ValidMountainArray(int[] arr) {
        if (arr.Length < 3) return false;

        int left = 0;
        int right = arr.Length - 1;

        while (left + 1 < arr.Length && arr[left] < arr[left + 1]) left ++;
        while (right > 0 && arr[right] < arr[right - 1]) right --;
        if (left == right && left != 0 && right != arr.Length - 1) return true;
	
        return false;
    }
}

Rust

impl Solution {
    pub fn valid_mountain_array(arr: Vec<i32>) -> bool {
        let mut i = 0;
        let mut j = arr.len() - 1;
        while i < arr.len() - 1 && arr[i] < arr[i + 1] {
            i += 1;
        }
        while j > 0 && arr[j] < arr[j - 1] {
            j -= 1;
        }
        i > 0 && j < arr.len() - 1 && i == j
    }
}