Problem Statement

Given an integer array arr, return true if arr is a valid mountain array. Otherwise, return false.

The array is called a valid mountain array if:

• arr.length > 2
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Examples

Example 1:

• Input: arr = [4, 5, 6, 7, 8, 7, 6, 5]
• Expected Output: true
• Justification: The elements increase from 4 to 8 and then decrease from 8 back to 5, forming a mountain shape.

Example 2:

• Input: arr = [1, 2, 3, 4, 5]
• Expected Output: false
• Justification: The elements only increase and there's no decrease after a peak, hence not forming a mountain.

Example 3:

• Input: arr = [9, 8, 7, 6, 5]
• Expected Output: false
• Justification: The elements decrease from the start without an initial increase, failing to form a mountain shape.

Solution

To solve this problem, we'll follow a two-phase approach that mirrors the structure of a mountain: ascending and descending. Initially, we'll iterate through the array, ensuring that each element is strictly larger than its predecessor, signifying an upward slope towards the peak. Upon reaching the peak, which is identified when the current element is no longer greater than the next, we transition to the descending phase. In this phase, we ensure that each subsequent element is strictly smaller, representing the downward slope of the mountain.

The algorithm succeeds if it finds both an ascending and descending sequence with at least one element in each, forming a valid mountain shape. This approach is effective because it closely follows the definition of a mountain array, requiring a strict increase followed by a strict decrease, and can be implemented efficiently.

Step-by-Step Algorithm

1. Initialize an Index Variable: Start with an index variable, i, set to 0. This variable will be used to iterate through the array.

2. Check for Ascending Order:

   • While i+1 is less than the array length and the current element is less than the next element (arr[i] < arr[i + 1]), increment i.
   • This loop checks for a strictly increasing sequence before the peak.

3. Validate Peak Existence:

   • Ensure that the peak is not at the start or end of the array. If i is 0 or i equals arr.length - 1, the array does not form a mountain shape, so return false.

4. Check for Descending Order:

   • After identifying the peak, continue checking the elements. While i+1 is less than the array length and the current element is greater than the next element (arr[i] > arr[i + 1]), increment i.
   • This loop ensures the sequence is strictly decreasing after the peak.

5. Verify End of Array:

   • If i equals arr.length - 1 by the end of the process, it means we have a valid mountain array. Return true.
   • If not, the array does not form a valid mountain shape. Return false.

Algorithm Walkthrough

Let's consider the input: arr = [4, 5, 6, 7, 8, 7, 6, 5].

1. Initialize i as 0.

2. Ascending Order Check:

   • Step 1: i = 0, arr[i] = 4, arr[i + 1] = 5. Since 4 < 5, increment i to 1.
   • Step 2: i = 1, arr[i] = 5, arr[i + 1] = 6. Since 5 < 6, increment i to 2.
   • Step 3: i = 2, arr[i] = 6, arr[i + 1] = 7. Since 6 < 7, increment i to 3.
   • Step 4: i = 3, arr[i] = 7, arr[i + 1] = 8. Since 7 < 8, increment i to 4.

3. Validate Peak Existence:

   • Now i = 4 and arr[i] = 8. The next element is 7, so we stop ascending. Since i is not 0 or arr.length - 1, we have a valid peak.

4. Descending Order Check:

   • Step 5: i = 4, arr[i] = 8, arr[i + 1] = 7. Since 8 > 7, increment i to 5.
   • Step 6: i = 5, arr[i] = 7, arr[i + 1] = 6. Since 7 > 6, increment i to 6.
   • Step 7: i = 6, arr[i] = 6, arr[i + 1] = 5. Since 6 > 5, increment i to 7.

5. Verify End of Array:

   • Now i = 7, which is arr.length - 1. We have successfully found a valid mountain array shape, so the algorithm returns true.