Thursday, November 22, 2018

941. Valid Mountain Array

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

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


Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true


Solution:

The idea is to:
1. check the array is increasing and find the peak
2. check the rest of array is decreasing

Since we check each element at most twice. The time complexity is O(n).


Code:


class Solution {
    public boolean validMountainArray(int[] A) {
        if (A == null || A.length < 3) {
            return false;
        }
        int peak = 0;
        while (peak + 1 < A.length) {
            if (A[peak + 1] <= A[peak]) {
                break;
            }
            peak++;
        }
        if (peak == 0 || peak == A.length - 1) {
            return false;
        }
        while (peak + 1 < A.length) {
            if (A[peak] <= A[peak + 1]) {
                return false;
            }
            peak++;
        }
        return true;
    }
}