algoadvance

Leetcode 941. Valid Mountain Array

Problem Statement

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

1. arr.length >= 3
2. There exists some index i (0 < i < arr.length - 1) such that:
   • arr[0] < arr[1] < ... < arr[i]
   • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

In other words, the array must have at least one peak element and on both sides of the peak, elements should strictly increase up to the peak and strictly decrease beyond the peak.

Clarifying Questions

1. Can the array have duplicates?
   • No, since it’s only decreasing or increasing, consecutive duplicates would not fit the strict comparison criteria.
2. Is a single peak sufficient for a valid mountain array?
   • Yes, there should only be one peak element to meet both increasing and decreasing conditions.

Strategy

1. Check if the size of the array is less than 3, in which case it cannot be a valid mountain array.
2. Use two pointers to iterate and check:
   • One pointer starts from the beginning of the array and increases as long as the next element is greater than the current element.
   • Another pointer starts from the end of the array and decreases as long as the previous element is greater than the current element.
3. Compare where the two pointers meet:
   • If they meet at a valid peak (not the start or the end), then the array forms a valid mountain array.
   • If not, it is not a valid mountain array.

Code

#include <vector>

bool validMountainArray(std::vector<int>& arr) {
    int n = arr.size();
    
    if (n < 3)
        return false;
    
    int left = 0;
    int right = n - 1;
    
    // Climb the mountain from the left
    while (left + 1 < n && arr[left] < arr[left + 1]) {
        left++;
    }
    
    // Climb the mountain from the right
    while (right - 1 >= 0 && arr[right] < arr[right - 1]) {
        right--;
    }
    
    // Check if the two pointers meet at the same peak point and if it's not at the start or the end
    return left > 0 && right < n - 1 && left == right;
}

Time Complexity

• Time Complexity: O(n) because we make a single pass from both the left and right ends of the array.
• Space Complexity: O(1) since we use a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?