Mountain Array

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

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:

• Count Inversions
• Hybrid QuickSort Algorithm
• In-place vs out-of-place algorithms
• Find a Pair with the given sum in a BST
• Create a mirror of an m–ary Tree
• Dutch National Flag Problem
• Construction of an Expression Tree
• Subarray with Sum k
• Maximum Sum Circular Subarray
• Move all zeros present in an array to the end