Check Array is a Valid Mountain or Not

Difficulty: Easy, Asked-in: Google, Amazon

Key Takeaway

  • An excellent problem to learn problem-solving using a single scan.
  • 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, array is a valid mountain when it is first 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, 6, 5, 3], 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, we first move up from left end to the peak and then move down from peak to the right end. So one basic idea would be to scan the array from left and check strictly increasing and then decreasing order of elements.

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

    int climb = 0
    while (climb < n - 1 && X[climb] < X[climb + 1])
      climb = climb + 1
    if (climb == 0 || climb == n - 1)
      return false
  • If peak is present at some middle element, we run another loop from that position to check strictly decreasing order or elements. If we reach the end, then 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 will be performing a single scan of the array or accessing each array element only once. So time complexity = O(n). Space complexity = O(1) i.e we are using constant extra space. 

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, their first peak point will be the same. In other words, both will meet at the only peak point in mountain array. Otherwise, if there is no valid mountain, their first peak point will be different. (Think!)

  • We initialise two variables left and right to climb from opposite ends i.e. left = 0, right = n - 1
  • Now using loop, we start climbing from the left end and reach the peak.

    while (left < n - 1 && X[left] < X[left + 1]) 
      left = left + 1
  • Using the loop, we start climbing from 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), both left and right pointers are at the same mountain peak, and we return true. Otherwise, both are at different mountain peaks, and we 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 will be traversing each element of the array only once, so 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 think of another approach to solve the problem by walking from left to right?
  • 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 the 2nd approach?
  • Here is a code snippet where we are tracking the down movement using a boolean variable downMove. Is this solution correct?

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

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!

Share feedback with us

More blogs to explore

Our weekly newsletter

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

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.