This problem is a part of Introduction to Data Structures Fun with Arrays - 101. Sub-heading of the section is searching for the items in an array.
Problem Statement
Given an array A of integers, return true if and only if it is a valid mountain array.
Observations
- Elements should be strictly increasing. Then a peak occurs, followed by a steady decrease.
- There can not be multiple mountain peaks in the array. Hence, if there exists a peak. The pattern would be as mentioned in point 1 above.
- The minimum number of elements in the array for a mountain peak to exist would be 3.
Solution Approach
- First, check the length of the array. Only if it is greater than 3. Then check the next conditions.
- Find the peak. The peak would be the point after which the value of elements strictly starts to strictly decrease.
- Be careful of the position of starting and ending in subsequent loops.
class Solution:
def validMountainArray(self, A: List[int]) -> bool:
result = False
if len(A) >= 3:
for x in range(0, len(A)-1):
if A[x+1] > A[x]:
result = True
else:
break
if result:
for index in range(x, len(A)-1):
if (A[index+1] < A[index]):
result = True
else:
result = False
break
return result
Learnings
- Time complexity - O(n)
- Solve multiple scenarios using a pen and paper first. Then code. :)
Top comments (4)
This problem can be found in Leetcode: leetcode.com/problems/valid-mounta...
My approach with test case:
Aren't the last two test cases wrong? The expected answer on leetcode returns false and not true. I am trying to solve this now!
@gabriel , yes you are right. I did not notice about the leetcode problem. I have updated the old answer.
Thank you for finding the bug.
This is a good one! I've done it in Java and C, C was harder (types and all stuff).