Valid Mountain Array
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
iwith0 < i < arr.length - 1such that:-
arr[0] < arr[1] < ... < arr[i - 1] < A[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
Constraints:
-
1 <= arr.length <= 104 -
0 <= arr[i] <= 104
Solution:
class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length, i = 0, j = n - 1;
while (i+1 < n && arr[i] <
arr[i + 1]) i++;
while (j > 0 && arr[j - 1] >
arr[j]) j--;
return i > 0 && i == j && j
< n - 1;
}
}
Here, in the problem it is clearly mentioned that it should be strictly
increasing and strictly decreasing. So, initially it starts increasing and at
some point it start strictly decreasing. Using this concept we are going to
solve this problem.
1) First while-loop is used to find index point where
it stops increasing [traversing from 0 to n-1].
2) Second while-loop is used to find index point where
it stops decreasing [traversing from n-1 to 0].
3) Finally we are returning boolean by checking conditions such as.,
a) i and j must be at same position.
b) i should be greater than 0
[minimum array should contain one increasing point]
c) j must be lesser than n-1
[minimum array should contain one decreasing point].
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section which
will be helpful for us to improve.
Comments
Post a Comment