Leetcode Mountain Array

Question

I've been working on longest mountain in array on Leetcode:

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

I've come up with a solution that passes the test but only beats 17% of javascript submissions. I just want to know if there's anything I can do with my code to optimize it's performance. Also please let me know if the code could be written better.

The idea is as followed. In a mountain array we have a start, peak, and an end. I keep track of when a mountain starts, when a mountain peaks and when a mountain ends. When the mountain ends i pop off my start value from the start stack and use the spread operator to add it to a result array which contains the peak and the end of a mountain.

For example the array [1,3,8]... the mountain starts at index 1, peaks at index 3 and ends at index 8. In order to find the length of the array I then subtract the end from the start.

A mountain can have multiple peaks and thus an array such as [[1,3,8],[8,13,18]] is possible. I'm handling this situation by having a maxDifference variable to store the maximum differences if a mountain is complete [start, peak, end].

var longestMountain = function(A) { let maxDifference = 0; let startPeakEnd = []; const start = []; const innerLoop = []; if(A[1]>A[0])start.push(0) else start.push(1); for(let i = 0; i < A.length; i++){ if(A[i-1]<A[i] && A[i+1]<A[i]){ startPeakEnd.push(i); }else if(A[i-1]>=A[i] && A[i+1]>=A[i]){ startPeakEnd.push(i); innerLoop.push([start.pop(),...startPeakEnd]); start.push(i) startPeakEnd = []; }else if(A[i+1]===undefined){ startPeakEnd.push(i); innerLoop.push([start.pop(),...startPeakEnd]); } } for(let item of innerLoop){ if(item.length===3){ if(item[2]-item[0]+1>maxDifference){ maxDifference=item[2]-item[0]+1; } } } return maxDifference; }; 

Answer 1

It would be better to try and use built in functions for iterating over arrays. It appears that you are trying to generate and store all possible mountains. This would not be necessary. This would be my approach.

var longestMountain = function(arr) { //get nodes that may be the peaks of mountains var candidates = arr.map(function(currentValue, index) { if (index == 0 || index === arr.length - 1) { return false; } else { return arr[index - 1] < currentValue && arr[index + 1] > currentValue; } }); //for each index, calculate the height of the slope where arr[i - 1] < arr[i] var increasingMountainCounts = arr.map(function(currentValue, index) { if (index == 0 || arr[index - 1] >= currentValue) { return 0; } else { return arr[index - 1] + 1; } }); //for each index, calculate the height of the slope where arr[i - 1] > arr[i] var decreasingMountainCounts = arr.reverse().map(function(currentValue, index) { if (index == 0 || arr[index - 1] >= currentValue) { return 0; } else { return arr[index - 1] + 1; } }); //for each candidate peak, get the height of the mountain with that peak var maxMountainHeight = 0; candidates.forEach(function(currentValue, index) { if (currentValue !== true) {} else { maxMountainHeight = Math.max(maxMountainHeight, increasingMountainCounts[index - 1] + decreasingMountainCounts[index + 1] + 1); } }); return maxMountainHeight; }; 

An alternative approach which uses more javascript array iterators but in my opinion makes the code a bit less readable.

var longestMountain = function(arr) { var candidates = arr.map(function(currentValue, index) { if (index == 0 || index === arr.length - 1) { return false; } else { return arr[index - 1] < currentValue && arr[index + 1] > currentValue; } }); var increasingMountainCounts = arr.map(function(currentValue, index) { if (index == 0 || arr[index - 1] >= currentValue) { return 0; } else { return arr[index - 1] + 1; } }); var decreasingMountainCounts = arr.reverse().map(function(currentValue, index) { if (index == 0 || arr[index - 1] >= currentValue) { return 0; } else { return arr[index - 1] + 1; } }); var maxMountainHeightAccumulator = (maxMountainHeight, currentValue, index) => { if (currentValue !== true) { return maxMountainHeight; } else { return Math.max(maxMountainHeight, increasingMountainCounts[index - 1] + decreasingMountainCounts[index + 1] + 1); } }; return candidates.reduce(maxMountainHeightAccumulator, 0); }; 

In terms of improving performance, this reminds me of the problem of finding the (contigious) subsequence with the maximum sum/product. That solution would probably require completely rewriting your code.