Valid Mountain Array - Leetcode Solution

Problem Description:

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:

arr.length >= 3 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]

Example 1:

Input: arr = [2,1] Output: false

Example 2:

Input: arr = [3,5,5] Output: false

Example 3:

Input: arr = [0,3,2,1] Output: true

Solution:

To solve this problem, we can use a two-pointer approach. We start by checking if the array has at least three elements. Then, we initialize two pointers i and j at the beginning and end of the array respectively.

We then move the i pointer to the right as long as arr[i] is strictly less than arr[i+1]. Similarly, we move the j pointer to the left as long as arr[j] is strictly less than arr[j-1].

If either i or j reaches the end of the array before we find a peak, we return false. If we do find a peak, we check if i and j are equal. If they are, we return true, otherwise we return false.

Here's the code:

class Solution { public: bool validMountainArray(vector<int>& arr) { int n = arr.size(); if(n < 3) return false; int i = 0, j = n-1; while(i < n-1 && arr[i] < arr[i+1]) i++; while(j > 0 && arr[j] < arr[j-1]) j--; if(i == 0 || j == n-1 || i != j) return false; return true; } };

Time Complexity:

The time complexity of this solution is O(n), where n is the number of elements in the array, since we only traverse the array once.

Space Complexity:

The space complexity of this solution is O(1), since we do not use any extra data structures.

1