Leetcode 941. Valid Mountain Array

Problem Explanation

The problem wants us to check whether the given array represents a mountain array or not. By definition, a mountain array first strictly increases and then strictly decreases. The peak should not be at the boundaries, meaning it should neither be the first element nor the last element. If any of these conditions fail, the array won't be considered as a mountain array.

For example, let's take an example [0, 3, 5, 2, 1]. This is a mountain array because 5 is the peak and all elements before 5 are in increasing order & all elements after 5 are in decreasing order.

Approach

The solution uses two pointers approach. It uses a left pointer starting from the first element and a right pointer starting from the last element of the array. It moves both pointers towards the center. For the left pointer, it moves as long as the next element is greater than the current one. Similarly, for the right pointer, it moves as long as the previous element is greater than the current one. Finally, it checks whether both pointers are at the same index and neither of them is at their initial position. If true, it means there is a peak and it's not at the boundary. Hence, the array is a mountain array.

Solutions

Python

1
2python
3class Solution:
4    def validMountainArray(self, arr):
5        if len(arr) < 3:
6            return False
7        
8        l = 0
9        r = len(arr) - 1
10        
11        while l+1 < len(arr) and arr[l] < arr[l+1]:
12            l += 1
13        while r > 0 and arr[r] < arr[r-1]:
14            r -= 1
15            
16        return l > 0 and r < len(arr) - 1 and l == r

Java

1
2java
3class Solution {
4    public boolean validMountainArray(int[] arr) {
5        if(arr.length < 3) {
6            return false;
7        }
8        
9        int l = 0;
10        int r = arr.length - 1;
11        
12        while(l+1 < arr.length && arr[l] < arr[l+1]) {
13            l++;
14        }
15        while(r > 0 && arr[r] < arr[r-1]) {
16            r--;
17        }
18        
19        return (l > 0 && r < arr.length - 1 && l == r);
20    }
21}

JavaScript

1
2javascript
3class Solution {
4    validMountainArray(A) {
5        if(A.length < 3){
6            return false;
7        }
8
9        let l = 0;
10        let r = A.length - 1;
11
12        while(l+1 < A.length && A[l] < A[l+1]) {
13            l++;
14        }
15        while(r > 0 && A[r] < A[r-1]) {
16            r--;
17        }
18
19        return (l > 0 && r < A.length - 1 && l == r);
20    }
21}

C++

1
2cpp
3class Solution {
4public:
5    bool validMountainArray(vector<int>& arr) {
6        if (arr.size() < 3) {
7            return false;
8        }
9
10        int l = 0;
11        int r = arr.size() - 1;
12
13        while (l + 1 < arr.size() && arr[l] < arr[l + 1]) {
14            ++l;
15        }
16        while (r > 0 && arr[r] < arr[r - 1]) {
17            --r;
18        }
19
20        return l > 0 && r < arr.size() - 1 && l == r;
21    }
22};

C#

1
2csharp
3public class Solution {
4    public bool ValidMountainArray(int[] arr) {
5        if (arr.Length < 3) {
6            return false;
7        }
8
9        int l = 0;
10        int r = arr.Length - 1;
11
12        while (l + 1 < arr.Length && arr[l] < arr[l + 1]) {
13            l++;
14        }
15        while (r > 0 && arr[r] < arr[r - 1]) {
16            r--;
17        }
18
19        return l > 0 && r < arr.Length - 1 && l == r;
20    }
21}

Conclusion

The proposed solutions cover different programming languages including Python, Java, JavaScript, C++, and C#. Each solution uses the dual pointer approach and ensures that the array has at least three elements, to begin with. In each solution, left pointer incremented while the next element is larger, and the right pointer decremented while the previous element is larger. This traversing continues towards the center of the array, stopping only when the condition of strictly increasing or strictly decreasing order is violated.

The final check is crucial. It verifies that the peak of the 'mountain' (where the left pointer equals the right pointer) is not at any boundary of the array and that both pointers have moved from their original positions (neither at the start nor at the end of the array). It returns true if these conditions hold. This is because, in that case, the array satisfies all the conditions of a mountain array. In all other cases, the function returns false, indicating that the array does not represent a mountain array.

Overall, the dual pointer strategy is efficient as it allows us to traverse the mountain in one pass, significantly reducing the time complexity of the algorithm. Thus, this solution is practical and efficient for checking whether an array is a mountain array or not.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ