Valid Mountain Array

Valid Mountain Array

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

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

• arr.length >= 3

• There exists some i with 0 < i < arr.length - 1 such that:

  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

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

Example 3:

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

Constraints:

• 1 <= arr.length <= 104

• 0 <= arr[i] <= 104

Solutions

🧠 Cpp

class Solution
{
public:
    //O(n) solution
    bool validMountainArray(vector<int>& A)
    {
        //empty is no mountain
        if(A.empty())
            return false;

        bool going_up = true;
        for(auto iter = ++begin(A); iter < end(A); ++iter)
        {
            //no flat
            if(*iter == *prev(iter))
               return false;

            //go up
            if(*prev(iter) < *iter)
            {
                //if we went up after we went down
                if(!going_up)
                    return false;
            }
            //go down
            else if(*prev(iter) > *iter )
            {
                //if we going down from the start
                if(prev(iter) == begin(A))
                    return false;
                //started to gow down
                if(going_up)
                    going_up = false;
            }           
        }

        //if we were going up all the time, return false
        return !going_up;

    }
};