Valid Mountain Array

Difficulty: Easy, Asked-in: Google, Amazon

Key Takeaway

  • An excellent problem to learn problem-solving using a single scan
  • Solution ideas are intuitive and easy to visualize
  • A good interview problem for beginners to start

Let’s understand the problem!

Given an array X[] of n integers, write a program to check the given array is a valid mountain array or not.

  • The array X[] is a mountain array if and only if n >= 3 and there exists some i (0 < i < n -1) such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n-1].
  • In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.

Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Examples

Input: X[] = [5, 2, 1, 4], Output: false

Input: X[] = [5, 8, 8], Output: false

Input: X[] = [1, 2, 4, 2], Output: true

Discussed Solution Approaches

Solution Approach 1: Traversing from left to right

Solution Approach 2: Traversing from opposite ends

Solution Approach 1: Traversing from left to right

Solution Idea and Steps

If there is a mountain then we first move up from left to the peak and then move down from peak to the right. So the basic idea would be : scan the array from the left and check the strictly increasing and then decreasing order of elements.

  • We start from the left end and initialize the variable climb to track the order of elements i.e. climb = 0.
  • Now we check the strictly increasing order and reach the peak by running a loop. If X[climb] < X[climb + 1] and climb < n - 1, then we are on the track of the increasing order and we move to the next element. We stop the loop if any one of the conditions becomes false.
  • By end of the loop, if the peak is present at first or the last element i.e. climb = 0 or climb = n - 1, then we return false. In other words, the peak can’t be the first or last element in the mountain.

    int climb = 0
    while (climb < n - 1 && X[climb] < X[climb + 1])
      climb = climb + 1
    if (climb == 0 || climb == n - 1)
      return false
    
  • If the peak is present at some middle element then similarly, we run a loop from that position to check the strictly decreasing order or elements. If we reach the end, the array is a valid mountain, otherwise, it’s not.

    while (climb < n - 1 && X[climb] > X[climb + 1])
      climb = climb + 1
    if (climb == n - 1)
      return true
    else 
      return false
      
    

Solution Pseudocode

boolean validMountain(int X[], int n) 
{
    int climb = 0
    while (climb < n - 1 && X[climb] < X[climb + 1])
        climb = climb + 1
    
    if (climb == 0 || climb == n-1)
        return false
            
    while (climb < n - 1 && X[climb] > X[climb + 1])
        climb = climb + 1
        
    if (climb == n-1)
        return true
    else 
        return false   
}

Solution Analysis

In the worst case, we are performing a single scan of the array i.e we are accessing each element of the array only once. Time complexity = O(n). Space complexity = O(1) i.e no extra space is used. 

Solution Approach 2: Traversing from opposite ends

Solution Idea and Steps

Here is another analogy of the solution. Suppose two people are climbing from the left and right end separately. If there is a valid mountain, then their first peak point will be the same. In other words, both will meet at the only peak point in the mountain array. Otherwise, if there is no valid mountain, then their first peak point would be different. (Think!)

  • Initialise the variable left and right i.e. left = 0, right = n - 1
  • Using the loop, climb from the left end and reach the peak.

    while (left < n - 1 && X[left] < X[left + 1]) 
          left = left + 1
    
  • Using the loop, climb the right end and reach the peak.

    while (right > 0 && X[right - 1] > X[right])
          right = right - 1
    
  • If (left > 0 && left == right && right < n  -  1) then both are at the same peak of the mountain, return true. Otherwise return false.

Solution Pseudocode

boolean validMountain(int X[], int n)
{
    left = 0, right = n - 1
    while (left < n - 1 && X[left] < X[left + 1]) 
        left = left + 1 
    
    while (right > 0 && X[right - 1] > X[right])
        right = right - 1
        
    if(left > 0 && left == right && right < n - 1)
        return true
    else 
        return false
}

Solution Analysis

In the worst case, we are traversing each element of the array only once. Time complexity = O(n), Space complexity = O(1) i.e we are using constant extra space.

Important note: We recommend learners transform the above pseudocodes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Enjoy programming!

Critical ideas to think!

  • Can we find another method to solve the problem by walking from left to right?
  • are our solutions working for all test cases? What will happen in the case of repeated values?
  • Can we solve this problem by counting the peak and valley in the given array? In the mountain array, Peak count = 1, Valley count = 0
  • What would be the best, worst and average case analysis of 2nd approach?
  • Here is a code snippet where we are tracking the down movement using a boolean variable down_move. Is this solution correct?

    boolean validMountain(int X[], int n)
    {
      if (n <= 2 || X[0] > X[1]) 
          return false
      boolean down_move = false
      for (int i = 2; i < n; i = i + 1)
      {
          if (X[i] < X[i - 1]) 
              down_move = true
          else if (X[i] == X[i - 1] || down_move) 
              return false
      }
      return down_move
    }
    

Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

Comparisons of time and space complexities

  • Traversing from left to right: Time = O(n), Space = O(1)
  • Traversing from opposite ends: Time = O(n), Space = O(1)

Similar coding questions to practice

Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!

More From EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.

Follow Us:

LinkedinMedium

© 2020 EnjoyAlgorithms Inc.

All rights reserved.