Valid Mountain Array

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.

Examples

Input: X[] = [5, 2, 1, 4], Output: false. The array starts by descending, so it doesn’t form a mountain.
Input: X[] = [1, 2, 6, 5, 3] , Output: true. The array strictly increases to a peak, then strictly decreases.
Input: X[] = [1, 2, 3, 4], Output: false. The array never descends after reaching its peak.
Input: X[] = [4, 3, 2, 1], Output: false. The array never ascends before descending.
Input: X[] = [1, 2, 2, 1], Output: false. The repeated 2s create a plateau at the peak.

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 the array forms a mountain, we first move up from the left end to the peak and then move down from the peak to the right end. So, one basic approach is to scan the array from left to right, checking that the elements are strictly increasing and then strictly decreasing.

We start at the left end and initialise the variable climb to track our position: climb = 0.
We then check for a strictly increasing order and move toward the peak using a loop. If climb < n - 1 and X[climb] < X[climb + 1], the sequence is still increasing, so we move to the next element. We stop the loop when either condition becomes false.
At the end of the loop, if the peak is at the first or last element, that is, if climb == 0 or climb == n - 1, we return false. In other words, the peak cannot be the first or last element in a 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

validMountain(X, n)
    climb = 0

    // Move uphill to find the peak
    while climb < n - 1 and X[climb] < X[climb + 1]
        climb = climb + 1

    // The peak cannot be the first or last element
    if climb == 0 or climb == n - 1
        return false

    // Move downhill from the peak
    while climb < n - 1 and X[climb] > X[climb + 1]
        climb = climb + 1

    // A valid mountain must descend all the way to the last element
    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 pseudocode

validMountain(X, n)
    left = 0
    right = n - 1

    // Move left uphill from the start
    while left < n - 1 and X[left] < X[left + 1]
        left = left + 1

    // Move right uphill from the end
    while right > 0 and X[right - 1] > X[right]
        right = right - 1

    // Both pointers must meet at an interior peak
    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.

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?

validMountain(X, n)
  if n <= 2 or X[0] > X[1]
      return false

  downMove = false

  for i from 2 to n - 1
      if X[i] < X[i - 1]
          downMove = true
      else if X[i] == X[i - 1] or 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)

Check Array is a Valid Mountain or Not

Let’s understand the problem

Examples

Discussed solution approaches

Traversing from left to right

Solution idea and steps

Solution pseudocode

Solution analysis

Traversing from opposite ends

Solution idea and steps

Solution pseudocode

Solution analysis

Critical ideas to think!

Comparison of time and space complexities

Similar coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs