Valid Mountain Array

The idea for this problem is to first find the index of the peak. Peak is defined as A[i-1] < A[i] > A[i+1].

class Solution {
    fun validMountainArray(A: IntArray): Boolean {
        if(A.size <= 1) return false
        // ascend and find the peak
        var i = 1
        while(i < A.size && A[i-1] < A[i]) i++
        i-- 
        // try to stop early by checking if the peak is in the first or last element
        if(i == 0 || i == A.size - 1) return false
        
        // then descend and make sure each succeeding element is smaller than previous
        while(i < A.size - 1){
            if(A[i] <= A[i+1]) return false
            i++
        }
        
        return true
    }
}
Runtime: 232 ms, faster than 36.36% of Kotlin online submissions for Valid Mountain Array.
Memory Usage: 37.7 MB, less than 100.00% of Kotlin online submissions for Valid Mountain Array.

During the ascend, each previous element should be smaller than the next element.

After the ascend, make sure that the peak we found is not the first nor the last because if it is, then it’s an invalid mountain.

During the descend, each element should be greater than the previous element. If we find any which breaks this constraint then we return false immediately.

comments powered by Disqus