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 < arr < … < arr[i – 1] < arr[i]
• arr[i] > arr[i + 1] > … > arr[length of array – 1]

1, 2, 3, 2, 1

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";
}
}

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));
}
}

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 