Valid Mountain Array – 941. LeetCode

Imagine you are hiking on a mountain trail, where the path first climbs up to a peak and then descends. To check if the trail is a “valid mountain”, the path must strictly go up and then strictly go down, with no flat or repeated sections. This problem determines whether a given array of numbers behaves like a mountain trail.

A valid mountain array must:

1. Be at least 3 elements long.

2. Have a single peak that is not at the start or the end of the array.

3. Strictly increase before the peak.

4. Strictly decrease after the peak.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;

        boolean increasing = true;
        int peakCount = 0;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) return false; // No flat sections
            if (increasing) {
                if (arr[i] < arr[i - 1]) {
                    increasing = false;
                    peakCount++;
                }
            } else {
                if (arr[i] >= arr[i - 1]) return false; // Descending fails
            }
        }

        return !increasing && peakCount == 1; // Must have descended after exactly one peak
    }
}

• Traverse the array while checking:
  • If numbers are initially decreasing and then decreasing.
  • If there is exactly one peak.
• Return false if there are any flat sections or multiple peaks.

Optimal Approach

Algorithm & Data Structure

• Algorithm: Two-Pointer Approach

• Data Structure: No additional data structure required.

Intuition:

Instead of scanning the array multiple times or maintaining extra state variables, use two pointers to independently climb the mountain from the left and descend from the right. If both pointers meet at the same peak, it’s a valid mountain.

• The two-pointer method directly focuses on the climbing and descending properties of the array, avoiding redundant checks.

• This simplifies the problem to verifying whether the peak lies in the middle and both pointers meet there.

Steps of Algorithm:

1. Handle edge cases where the array length is less than 3.

2. Use two pointers:

• Start one pointer from the left and climb up.

• Start another pointer from the right and descend down.

3. Check if both pointers meet at the same peak and cover the entire array.

4. Return true if valid; otherwise, false.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false; // A mountain must have at least 3 elements

        int left = 0;
        int right = arr.length - 1;

        // Climb up from the left
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
            left++;
        }

        // Climb down from the right
        while (right - 1 >= 0 && arr[right] < arr[right - 1]) {
            right--;
        }

        // Check if both pointers meet at the same peak
        return left > 0 && right < arr.length - 1 && left == right;
    }
}

Line-By-Line Explanation

Step 1: Check the Input

if (arr.length < 3) return false;

• The algorithm check if the array has fewer than 3 elements because a mountain requires at least one increasing and one decreasing slope, which is impossible with fewer elements.

Step 2: Initialize Two Pointers

int left = 0;
int right = arr.length - 1;

• Two pointers are initialized: one starts from the leftmost position the other from the rightmost position. These points move toward the center to identify the mountain peak.

Step 3: Iterate From Left

while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
    left++;
}

• Increment the left pointer as long as the current element is smaller than the next one
• To access arr[left + 1] safely, we must ensure that left + 1 is within bound of the array.
• Ensures correctness by directly check the increasing slope.

Step 4: Iterate From Right

while (right - 1 >= 0 && arr[right] < arr[right - 1]) {
    right--;
}

• Decrement the right pointer as long as the current element is larger than the previous one (arr[right] < arr[right – 1]), ensuring a strictly decreasing slope.

Step 5: Validate The Mountain

return left > 0 && right < arr.length - 1 && left == right;

• Check if:
  • left > 0: The left pointer moved beyond the start, confirming an increasing slope.
  • right < arr.length – 1: The pointer moved beyond the end, confirming a decreasing slope.
  • left == right: Both pointers meet at the peak, indicating a single valid mountain peak.

Why This Code Works

• No Extra Memory: Unlike using an array or stack to track slopes, this algorithm uses pointers, making it memory-efficient.

• Direct Access: Pointers operate directly on the input array, avoiding the overhead of additional data structures.

• Simplicity: More complex approaches, such as recursion or sorting, might make the code harder to read and maintain.

This algorithm balances simplicity, efficiency, and clarity, making it well-suited for competitive programming and technical interviews.