Problem Description

You are given an array of integers arr. Your task is to determine if this array represents a valid mountain array.

A mountain array must satisfy the following conditions:

1. The array must have at least 3 elements (arr.length >= 3)

2. There must exist some index i where 0 < i < arr.length - 1 such that:

   • The elements strictly increase from the start up to index i: arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
   • The elements strictly decrease from index i to the end: arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

In other words, the array should first strictly increase to reach a peak, then strictly decrease from that peak. The peak cannot be at the first or last position of the array.

Return true if the array is a valid mountain array, otherwise return false.

For example:

• [0, 3, 2, 1] is a valid mountain array (increases to 3, then decreases)
• [3, 5, 5] is not valid (contains equal consecutive elements)
• [0, 1, 2, 3] is not valid (only increases, never decreases)
• [3, 2, 1] is not valid (only decreases, never increases)

Intuition

The key insight is that a valid mountain array has exactly one peak - a point where the array transitions from strictly increasing to strictly decreasing. We can think of this peak as the "summit" of the mountain.

Instead of checking every element sequentially, we can approach this problem from both ends simultaneously. Imagine two hikers: one starting from the left side of the mountain and climbing up, and another starting from the right side and also climbing up (which means going backwards through the array).

The left hiker will keep climbing as long as each next step is higher than the current one (arr[i] < arr[i + 1]). They'll stop when they can't go higher anymore - this should be at the peak.

Similarly, the right hiker moves leftward as long as each previous element is higher than the current one (arr[j - 1] > arr[j]). They'll also stop when they can't climb higher - which should also be at the peak.

If both hikers meet at the same position (i == j), and neither got stuck at the very beginning or end of the array, then we've found a valid mountain with a single peak. If they stop at different positions, it means either:

• There's a plateau (flat section) somewhere
• The array doesn't strictly increase then decrease
• There are multiple peaks

This two-pointer approach elegantly verifies both the ascending and descending requirements while also ensuring there's exactly one peak in the valid range.

Solution Approach

The implementation uses a two-pointer technique to efficiently validate the mountain array:

Step 1: Initial Length Check

if n < 3:
    return False

First, we check if the array has at least 3 elements. If not, it cannot form a mountain, so we immediately return false.

Step 2: Find the Peak from the Left

i = 0
while i + 1 < n - 1 and arr[i] < arr[i + 1]:
    i += 1

We initialize pointer i at position 0 and move it rightward as long as the array is strictly increasing (arr[i] < arr[i + 1]). The condition i + 1 < n - 1 ensures that the peak cannot be at the last position. When this loop ends, i should be at the peak position if the array is a valid mountain.

Step 3: Find the Peak from the Right

j = n - 1
while j - 1 > 0 and arr[j - 1] > arr[j]:
    j -= 1

We initialize pointer j at the last position and move it leftward as long as the array is strictly decreasing when viewed from right to left (arr[j - 1] > arr[j]). The condition j - 1 > 0 ensures that the peak cannot be at the first position. When this loop ends, j should also be at the peak position if the array is valid.

Step 4: Validate the Mountain

return i == j

If both pointers meet at the same position (i == j), it confirms:

• There's a strictly increasing sequence from the start to position i
• There's a strictly decreasing sequence from position j to the end
• There's exactly one peak in the array
• The peak is neither at the first nor the last position

If i != j, it means the array either has a plateau, multiple peaks, or doesn't follow the strict increase-then-decrease pattern required for a mountain array.

Time Complexity: O(n) where n is the length of the array, as we traverse the array at most once from each end.

Space Complexity: O(1) as we only use two pointers regardless of input size.

Example Walkthrough

Let's walk through the solution with the array [1, 3, 5, 4, 2]:

Step 1: Initial Setup

• Array: [1, 3, 5, 4, 2], length n = 5
• Since n >= 3, we proceed
• Initialize i = 0 (left pointer) and j = 4 (right pointer)

Step 2: Left Pointer Climbing Up

• Start at i = 0: Check if arr[0] < arr[1] → 1 < 3 ✓, move i to 1
• At i = 1: Check if arr[1] < arr[2] → 3 < 5 ✓, move i to 2
• At i = 2: Check if arr[2] < arr[3] → 5 < 4 ✗, stop
• Left pointer stops at i = 2 (the peak)

Step 3: Right Pointer Climbing Up (from right)

• Start at j = 4: Check if arr[3] > arr[4] → 4 > 2 ✓, move j to 3
• At j = 3: Check if arr[2] > arr[3] → 5 > 4 ✓, move j to 2
• At j = 2: Check if arr[1] > arr[2] → 3 > 5 ✗, stop
• Right pointer stops at j = 2 (the peak)

Step 4: Validation

• Both pointers meet at position 2: i == j == 2 ✓
• This confirms element at index 2 (value 5) is the single peak
• The array strictly increases [1, 3, 5] then strictly decreases [5, 4, 2]
• Return true - this is a valid mountain array!

Counter-Example: [1, 2, 2, 3]

• Left pointer: Moves from 0 to 1 (1 < 2 ✓), stops at 1 (2 < 2 ✗)
• Right pointer: Moves from 3 to 2 (2 > 3 ✗), stays at 3
• Pointers don't meet: i = 1, j = 3
• Return false - not a valid mountain (has equal consecutive elements)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array.

The algorithm uses two pointers that traverse the array from opposite ends:

• The first pointer i starts from the beginning and moves forward while arr[i] < arr[i + 1], which takes at most O(n) iterations
• The second pointer j starts from the end and moves backward while arr[j - 1] > arr[j], which also takes at most O(n) iterations
• Since each element is visited at most once by either pointer, the total time complexity is O(n)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables n, i, and j are the only additional space used
• No additional data structures are created
• The space usage does not depend on the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Boundary Conditions in While Loops

The Problem: A common mistake is using incorrect boundary conditions in the while loops, such as:

# Incorrect versions:
while left_pointer < n - 1 and arr[left_pointer] < arr[left_pointer + 1]:
    left_pointer += 1

while right_pointer > 0 and arr[right_pointer - 1] > arr[right_pointer]:
    right_pointer -= 1

Why It's Wrong:

• The first loop with left_pointer < n - 1 would allow the peak to be at position n - 1 (the last element)
• The second loop with right_pointer > 0 would allow the peak to be at position 0 (the first element)
• This violates the mountain array requirement that the peak cannot be at the boundaries

The Solution: Use the correct boundary conditions:

while left_pointer + 1 < n - 1 and arr[left_pointer] < arr[left_pointer + 1]:
    left_pointer += 1

while right_pointer - 1 > 0 and arr[right_pointer - 1] > arr[right_pointer]:
    right_pointer -= 1

Pitfall 2: Not Handling Arrays That Only Increase or Only Decrease

The Problem: Forgetting that arrays like [1, 2, 3, 4] (only increasing) or [4, 3, 2, 1] (only decreasing) are not valid mountains. Some might assume that if one pointer moves, it's sufficient.

Why It Happens: If the array only increases, left_pointer will reach n - 2 but right_pointer will stay at n - 1. If the array only decreases, right_pointer will reach 1 but left_pointer will stay at 0. In both cases, left_pointer != right_pointer.

The Solution: The final check return left_pointer == right_pointer correctly handles this. Both pointers must meet at the same position for a valid mountain.

Pitfall 3: Confusing Strict Inequality with Non-Strict

The Problem: Using <= or >= instead of < and >:

# Incorrect:
while left_pointer + 1 < n - 1 and arr[left_pointer] <= arr[left_pointer + 1]:
    left_pointer += 1

Why It's Wrong: Mountain arrays require strictly increasing and decreasing sequences. Equal consecutive elements like in [1, 2, 2, 1] would make it invalid, but using <= would incorrectly accept it.

The Solution: Always use strict inequalities (< and >) to ensure no plateaus or equal consecutive elements are allowed.

Pitfall 4: Off-by-One Errors in Index Checking

The Problem: Incorrectly checking array bounds when accessing arr[i + 1] or arr[j - 1]:

# Potential index out of bounds:
while arr[left_pointer] < arr[left_pointer + 1]:  # Missing boundary check
    left_pointer += 1

Why It's Dangerous: Without proper boundary checks, arr[left_pointer + 1] could cause an index out of bounds error when left_pointer reaches n - 1.

The Solution: Always include boundary checks before array access:

while left_pointer + 1 < n - 1 and arr[left_pointer] < arr[left_pointer + 1]:
    left_pointer += 1

Note that the boundary check must come before the array comparison due to short-circuit evaluation.