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 if the 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, the 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 at least 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

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 code C++

bool validMountain(int X[], int n) 
{
    int climb = 0;
    
    // Find the peak of the mountain
    while (climb < n - 1 && X[climb] < X[climb + 1]) 
        climb = climb + 1;
    
    // Return false if the peak is at the beginning or end
    if (climb == 0 || climb == n - 1) 
        return false;
    
    // Traverse down the mountain
    while (climb < n - 1 && X[climb] > X[climb + 1]) 
        climb = climb + 1;
    
    // Return true if the end of the mountain is reached
    if (climb == n - 1) 
        return true;
    else
        return false;
}

Solution code Python

def validMountain(X, n):
    climb = 0
    while climb < n - 1 and X[climb] < X[climb + 1]:
        climb = climb + 1

    if climb == 0 or climb == n-1:
        return False

    while climb < n - 1 and 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. 

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 code C++

bool validMountain(int X[], int n) 
{
    int left = 0, right = n - 1;
    
    // Traverse up the mountain from left side
    while (left < n - 1 && X[left] < X[left + 1])
        left = left + 1;
    
    // Traverse up the mountain from right side
    while (right > 0 && X[right - 1] > X[right])
        right = right - 1;
        
    // Check if both pointer meet at the same peak
    if (left > 0 && left == right && right < n - 1)
        return true;
    else
        return false;
}

Solution code Python

def validMountain(X, n):
    left = 0
    right = n - 1
    while left < n - 1 and X[left] < X[left + 1]:
        left = left + 1

    while right > 0 and X[right - 1] > X[right]:
        right = right - 1

    if left > 0 and left == right and 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 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 pseudocode 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
  }

Comparison 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

• Move zeroes to the end
• Number of buildings facing the sun
• Find equilibrium index in an array
• Remove duplicates from sorted array
• Minimum number of removals to make mountain array
• Find whether a subarray is in form of a mountain or not

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!