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).

Answer 3

Your AscOrDes function is not working properly: it will always exit at the first iteration:

int AscOrDes(int a[], int first, int last)
{
    int i;
    printf("Check array from %d to %d\n", first, last);
    for(i=first; i<last; i++)
    {
        if(a[i]>a[i+1]) {
            printf("a[%d]=%d > a[%d]=%d, so return 1\n", i, a[i], i+1, a[i+1]);
            return(1);
        }
        else if(a[i]<a[i+1]) {
            printf("a[%d]=%d < a[%d]=%d, so return 1\n", i, a[i], i+1, a[i+1]);
            return(2);
        }
    }
    return 0;
}

However, I think you can probably evaluate the array more efficiently, something like this --

int state = 0;     // 0 = waiting for increase, 1 = incr, 2 = decr

for (i = 1; i < n; i++) {
    if (a[i-1] == a[i]) {
        // Equality is an immediate failure.
        printf("False\n"); exit(0);
    }
    if (a[i-1] < a[i]) {
        // We found an increase. This is valid in states 0 or 1.
        if (2 == state) {
            printf("False\n"); exit(0);
        }
        state = 1;
    } else {
        // Found a decrease. This is valid in state 1 or 2.
        if (0 == state) {
           printf("False\n"); exit(0);
        }
        state = 2;
    }
}
// At the end, we must be in state 2 (decrease after an increase).
if (2 != state) {
    printf("False\n"); exit(0);
}
printf("True\n");

Answer 4

Here is how I would do it in Python:

array = [3, 4, 5, 6, 9, 10, 11, 19, 6, 3, 2]


def is_strict_mountain(arr: list):
    maxim = 0
    prev = 0
    max_reached = False
    for element in arr:
        if element > maxim:
            maxim = element
        if element <= prev:
            max_reached = True
        if element >= prev and max_reached:
            return False
        prev = element
    return True


print(is_strict_mountain(array))

Here is how I would do it in C:

#include <stdio.h>

#define MIN_INT -2147483648

typedef enum {
    false, true
} bool;

bool is_strict_mtn(const int *array, int numElements) {
    if (array == NULL) {
        return false;
    }
    int max = MIN_INT;
    int prev = MIN_INT;
    bool max_reached = false;
    int count = 0;
    while (count++ < numElements) {
        if (*array > max) {
            max = *array;
        }
        if (*array <= prev) {
            max_reached = true;
        }
        if (*array >= prev && max_reached) {
            return false;
        }
        prev = *array++;
    }
    return true;
}

int main() {

    int arr[] = {5, 6, 7, 9, 12, 67, 56, 44, 23, 11, 5, 3, 1};

    if (is_strict_mtn(arr, 13)) {
        printf("The array is a mountain.\n");
        return 0;
    }
    printf("The array is not a mountain.\n");

    return 0;
}

Answer 5

you need keep tracking of increments and decrements I used array named delta if there is increment assign delta[i]=1 if there is decrement assign delta[i]=-1 count 1 s if they equal to last-1 then this part has increments count -1 s if they equal to last-1 then this part has increments

#include<stdio.h>
 int delta[1000];

 int AscOrDes (int a[], int first, int last) 
{
 for (int i=0;i<1000;i++)  delta[i]=0;
 int r = 0;
  
 int i;  
     
int c = 0;
           
for (i = first; i <= last && (i + 1) <= last; i++)
       
  {
      
 if((a[i+1] - a[i]) > 0){
     
     delta[i]=1;
 }
 else{
 delta[i]=-1;
     
 }

 
}
  
 
for (i = first; i <= last && (i + 1) <= last; i++)
    
  {
      
 if (delta[i] > 0)
    
 {

c++;
    
}
  
      else if (delta[i] < 0)
    
    {
      
 
c--;
    
 
}
 
}
  
if (c  >= (last - first))
    
return 1;
  
if (c*-1 >= (last - first))

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 - 1);
  
if (r1 == 1 && r2 == 2 && big != 0 && big != n - 1)
    
 
printf ("True");
  
  else
    
printf ("False");
  
return 0;

}


 
 

Answer 6

from numpy import sign

a = [1, 3, 4, 6, 5, 7, 2, 0]

trend = [sign(a[i+1]-a[i]) for i in range(len(a)-1)]
change = [trend[i+1]-trend[i] for i in range(len(trend)-1)]
print(f'{a} is a mountain: {(trend[0] == 1) and (0 not in trend) and (2 not in change)}')

---

• trend[0] == 1 to ensure the list starts by ascending.
• 0 not in trend to exclude a list with a plateau.
• 2 not in change to exclude descent followed by ascend.

Example:

• a: 1, 3, 3, 4, 3, 5, 4, 2
• trend: 1, 0, 1, -1, 1, -1, -1
• change: -1, 1, -2, 2, -2, 0

Answer 7

Consume the ascending half with dropwhile, then consume the descending half with all.

from itertools import dropwhile, pairwise

def is_mountain(a):
    return all(a>b for a,b in dropwhile(lambda x: x[0]<x[1], pairwise(a)))

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

Answer 8

State-oriented programming: state starts as "up", and becomes "down" the first time a < b is false.

from itertools import pairwise, starmap

def is_mountain(a):
    def p(a,b):
        return (p.going == "up" and a < b) or setattr(p, 'going', "down") or a > b
    p.going = "up"
    return all(starmap(p,pairwise(a)))

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