LeetCode – Valid Mountain Array Posted by

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;
};