Valid Mountain Array

Question

I was wondering if there is a programmatic way to determine if an array has the pattern of a perfect mountain, without valleys. (Example in the image)

Source: https://leetcode.com/problems/valid-mountain-array/

Edit:

My attempt in C:

#include<stdio.h>

int AscOrDes(int a[], int first, int last)
{
    int i;
    for(i=first; i<last; i++)
    {
        if(a[i]>a[i+1])
            return(1);
        else if(a[i]<a[i+1])
            return(2);
    }
    return 0;
}

int main() {
    int a[1000],n,i,big=0,r1,r2;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0; i<n; i++)
    {
        if(a[i]>=a[big])
            big=i;
    }
    r1=AscOrDes(a, 0, big);
    r2=AscOrDes(a, big, n);
    if(r1==2 && r2==1 && big!=0 && big!=n-1)
        printf("True");
    else
        printf("False");
    return 0;
}

The above code doesn't work for the following inputs:

8
1 3 2 5 4 3 2 0

It gives the output:

True

Even though it isn't a perfect mountain array.

What I have done in my program is check which element is the largest (big), and checked if the elements on the left side of the largest element are in ascending order and those on the right side are in descending order (how the mountain should be).

Answer 1

Will try this way:

def is_moutain(A):
    i = 1

    N = len(A)
    
    while i < N and A[i] > A[i-1]:   # go on if ascending, and more items existing 
        i += 1
        
    if i == 1 or i == N:
        return False
    
       
    while N > i and A[i] < A[i-1]:   # at the descending point...
        i += 1

    return i == N
 
if __name__ == '__main__':

    print(is_moutain([0, 2, 3, 4, 5, 3, 1]))    # True
    print(is_moutain([0, 2, 3, 4, 5, 2, 4]))    # False 

Answer 2

Here's a Python solution using itertools.groupby:

import itertools

def is_mountain(arr):
    return [u for u, _ in itertools.groupby(
        (b - a for a, b in zip(arr, arr[1:])),  # slope as difference
        lambda v: v // abs(v) if v else v       # slope as unit vector
    )] == [1, -1]  # strictly increasing, then decreasing

print(is_mountain([0, 2, 3, 4, 5, 2, 1, 0]))  # True
print(is_mountain([0, 2, 3, 3, 5, 2, 1, 0]))  # False

Given the sample input:

[0, 2, 3, 3, 5, 2, 1, 0]

the first generator (b - a for a, b in zip(...)) subtracts each pair of adjacent elements to produce a sequence of the changes in elevation (the individual slopes):

[2, 1, 0, 2, -3, -1, -1]

The v // abs(v) lambda expression that's used as the key argument to itertools.groupby normalizes those by dividing each by its magnitude, producing a sequence of unit vectors (1 for increasing, -1 for decreasing):

[1, 1, 0, 1, -1, -1, -1]

itertools.groupby combines identical adjacent elements, producing:

[1, 0, 1, -1]

We can then simply define a "mountain" as a list for which going through the above process results in the exact result [1, -1] (all increases followed by all decreases).