Mountain Array

Posted in /  

Mountain Array

Vinay Khatri
Last updated on June 23, 2022

    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:

    Leave a Comment on this Post

    0 Comments