LeetCode – Valid Mountain Array

Link: https://leetcode.com/problems/valid-mountain-array/

Solution 1 – Walking from left and right:

• walking the mountain from left – increment l for each valid ascending
• walking the mountain from right – increment r for each valid descending
• if i equals r, arr is a valid mountain array, as there was constant ascending as descending

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    var l = 0;
    var r = arr.length - 1;

    while(arr[l] < arr[l+1])
        l++;

    if(l === 0 || l === arr.length - 1)
        return false;

    while(arr[r] < arr[r-1])
        r--;

    return l == r;
};

Time Complexity: O(n) where N is the length of the array

Space Complexity: O(1), constant space

---

Solution 2 – Walking up and down:

• walk up the mountain – increment i for each valid ascending
• sanity check after ascending, if i is the first or last element of the array, return false as is not a valid mountain array
• walk down the mountain – counts how many descends
• arr is a valid mountain array if i (number of ascends + descends) equals arr.length – 1 (last index)

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    var i = 0;
    var N = arr.length;

    while(arr[i] < arr[i+1])
        i++;

    if(i === 0 || i === arr.length - 1)
        return false;

    while(arr[i] > arr[i+1])
        i++;

    return i == N - 1;
};

Time Complexity: O(n) where N is the length of the array

Space Complexity: O(1), constant space

Solution 3 – using booleans to keep track of increasing decreasing:

• iterate through the array.
• check if increasing (arr[i] < arr[i+1]). If there was a mountain decrease before (decreasing === true), return false early as it’s not a valid mountain if it has more than 1 peak.
• check if decreasing (arr[i] > arr[i+1]). If the mountain never increased before this decrease (increasing === false) return false early as the mountain can’t decrease without having an increase before.

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    var increasing = false;
    var decreasing = false;

    for(var i = 0; i < arr.length - 1; i++)
    {
        if (arr[i] < arr[i+1])
        {
            if (decreasing === true) return false;
            increasing = true;
        }
        else if (arr[i] > arr[i+1])
        {
            if (increasing === false) return false;
            decreasing = true;
        } else
            return false;
    }
    return increasing && decreasing;
};

Solution 4 – using peak index

• finding the peak index
• looking left, if anything else than increasing return false
• sanity check after looking to the left side, if l is the first or last element of the array, return false as is not a valid mountain array
• looking right, if anything else than decreasing return false

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    var peakIndex = arr.indexOf(Math.max(...arr));
    var l = 0;
    var r = arr.length - 1;

    while(l < peakIndex)
    {
        if (arr[l] >= arr[l+1]) return false;
        l++;
    }

    if (l === 0 || l === r) return false;

    while(r > peakIndex)
    {
        if (arr[r] >= arr[r-1]) return false;
        r--;
    }
    
    return true;
};