algoadvance

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 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]

Clarifying Questions

1. Can the array have duplicate elements?
   • No, as per the problem definition, a valid mountain array must strictly increase and then strictly decrease, implying no duplicates that disrupt this pattern.
2. Is the peak in the middle of the array?
   • Yes, the peak must be somewhere in the array such that it splits the array into a strictly increasing part followed by a strictly decreasing part.
3. Should the array be traversed more than once?
   • Ideally, a single pass through the array would be optimal for checking the conditions.

Strategy

1. Initial Checks:
   • If the array length is less than 3, return false as it cannot form a mountain array.
2. Two-pointer Strategy:
   • Use two pointers starting from 0 and the end of the array respectively, and move towards the center while checking the increasing and decreasing parts of the mountain array.
   • Move the left pointer until it no longer forms a strictly increasing sequence.
   • Move the right pointer until it no longer forms a strictly decreasing sequence.
   • A valid mountain array will have the left and right pointers meeting at the same peak index.

Code

def validMountainArray(arr):
    n = len(arr)
    if n < 3:
        return False

    left, right = 0, n - 1

    # Climb up from left
    while left + 1 < n and arr[left] < arr[left + 1]:
        left += 1

    # Climb up from right
    while right - 1 >= 0 and arr[right] < arr[right - 1]:
        right -= 1

    # left and right should point to the same peak index
    return left > 0 and right < n - 1 and left == right

# Example usage
arr = [2, 1]
print(validMountainArray(arr))  # Output: False

arr = [3, 5, 5]
print(validMountainArray(arr))  # Output: False

arr = [0, 3, 2, 1]
print(validMountainArray(arr))  # Output: True

Time Complexity

• Time Complexity: O(n), where n is the length of the array. We traverse the array with two pointers in a single pass.
• Space Complexity: O(1), as we use a constant amount of additional memory regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• 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?