Knowledge Guide
Home › DSA › Company Practice

easy Valid Mountain Array

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:

Examples

Example 1:

Example 2:

Example 3:

Try it yourself

Try solving this question here:

✅ Solution Valid Mountain Array

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.
Image
Image

Code

java
public class Solution {

  // Method to check if the given array is a valid mountain array
  public boolean validMountainArray(int[] arr) {
    int i = 0;
    // Ascend: Ensure the array is strictly increasing at the start
    while (i + 1 < arr.length && arr[i] < arr[i + 1]) {
      i++;
    }

    // Check for the peak's existence: It shouldn't be the first or last element
    if (i == 0 || i == arr.length - 1) {
      return false;
    }

    // Descend: Ensure the array is strictly decreasing after the peak
    while (i + 1 < arr.length && arr[i] > arr[i + 1]) {
      i++;
    }

    // Check if we've reached the end of the array
    return i == arr.length - 1;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(
      solution.validMountainArray(new int[] { 4, 5, 6, 7, 8, 7, 6, 5 })
    ); // true
    // Example 2
    System.out.println(
      solution.validMountainArray(new int[] { 1, 2, 3, 4, 5 })
    ); // false
    // Example 3
    System.out.println(
      solution.validMountainArray(new int[] { 9, 8, 7, 6, 5 })
    ); // false
  }
}

Complexity Analysis

Time Complexity:

The algorithm scans the array at most twice. The first scan is to check for the strictly increasing sequence until the peak is reached, and the second scan checks for the strictly decreasing sequence after the peak. Since both scans are linear and there are no nested iterations, the time complexity is , where n is the length of the array.

Space Complexity:

The algorithm uses a fixed amount of space. The space used does not scale with the input size, resulting in constant space complexity.

🤖 Don't fully get this? Learn it with Claude

Stuck on Valid Mountain Array? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Valid Mountain Array** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Valid Mountain Array** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Valid Mountain Array**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Valid Mountain Array**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Longest Common PrefixIsomorphic Strings →