Mountain Array

By | December 30, 2021

Problem

Given an array of integers, check if it is a mountain array or not. An array is called a mountain array if:

  1. Length of array >= 3
  2. There exists some i with 0 < i < (length of array) – 1 such that:
    • arr[0] < arr[1] < … < arr[i – 1] < arr[i]
    • arr[i] > arr[i + 1] > … > arr[length of array – 1]

Sample Input

1, 2, 3, 2, 1

Sample Output

True

Explanation

The array strictly increases upto index 2 and then strictly decreases.

Approach

The problem can be framed as follows:

Two people climb from left and from right separately on a mountain.

If they are climbing the same mountain, they will meet at the same point.

We will use two variables: one will point at the 0-th index and the other will point at the last array index and start moving the pointers towards the right and left respectively. In the end, we just check if both of them are at the same index.

Complexity Analysis

The time complexity is O(N) with no extra space required

Vamware

C++ Programming

#include <iostream>
#include<vector>

using namespace std;

// function to check mountain array
bool validMountainArray(vector<int>& A) {
    int n = A.size(), i = 0, j = n - 1;

    // move right towards array
    while (i + 1 < n && A[i] < A[i + 1]) i++;

    // move left towards array
    while (j > 0 && A[j - 1] > A[j]) j--;

    // if the two pointers meet at same point, return true
    return i > 0 && i == j && j < n - 1;
}

int main() {

    // initialize array
    vector<int>A{1, 2, 3, 2, 1};

    if(validMountainArray(A))
     {
       cout<<"True";
     }
    else
    { 
         cout<<"False";
    }
}

Output

1

Java Programming

import java.io.*;
class Solution {
    
    // function to check mountain array
    public static boolean validMountainArray(int[] A) {
        int n = A.length, i = 0, j = n - 1;
        
        // move right towards array
        while (i + 1 < n && A[i] < A[i + 1]) i++;
        
        // move left towards array
        while (j > 0 && A[j - 1] > A[j]) j--;
        
        // if the two pointers meet at same point, return true
        return i > 0 && i == j && j < n - 1;
    }

    public static void main (String[] args) {

        // initialize array
        int[] A = {1, 2, 3, 2, 1};

        System.out.println(validMountainArray(A));
    }
}

Output

true

Python Programming

# function to check mountain array
def validMountainArray(A):
    i, j, n = 0, len(A) - 1, len(A)

    # move right towards array
    while i + 1 < n and A[i] < A[i + 1]: i += 1

    # move left towards array
    while j > 0 and A[j - 1] > A[j]: j -= 1

    # if the two pointers meet at same point, return true
    return 0 < i == j < n - 1

# initialize array
A = [1, 2, 3, 2, 1]

print(validMountainArray(A))

Output

True

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *