Difficulty: Easy, Asked-in: Google, Amazon
Key Takeaway
Given an array X[] of n integers, write a program to check the given array is a valid mountain array or not.
The array X[] is a mountain array if and only if n >= 3 and there exists some i (0 < i < n -1) such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n-1]. In other words, array is a valid mountain when it is first strictly increasing and then strictly decreasing.
Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Examples
Input: X[] = [5, 2, 1, 4], Output: false
Input: X[] = [5, 8, 8], Output: false
Input: X[] = [1, 2, 6, 5, 3], Output: true
Solution approach 1: Traversing from left to right
Solution approach 2: Traversing from opposite ends
If there is a mountain, we first move up from left end to the peak and then move down from peak to the right end. So one basic idea would be to scan the array from left and check strictly increasing and then decreasing order of elements.
By end of the loop, if peak is present at first or last element i.e. climb = 0 or climb = n - 1, we return false. In other words, peak can’t be the first or last element in the mountain array.
int climb = 0
while (climb < n - 1 && X[climb] < X[climb + 1])
climb = climb + 1
if (climb == 0 || climb == n - 1)
return false
If peak is present at some middle element, we run another loop from that position to check strictly decreasing order or elements. If we reach the end, then array is a valid mountain, otherwise, it’s not.
while (climb < n - 1 && X[climb] > X[climb + 1])
climb = climb + 1
if (climb == n - 1)
return true
else
return false
boolean validMountain(int X[], int n)
{
int climb = 0
while (climb < n - 1 && X[climb] < X[climb + 1])
climb = climb + 1
if (climb == 0 || climb == n-1)
return false
while (climb < n - 1 && X[climb] > X[climb + 1])
climb = climb + 1
if (climb == n - 1)
return true
else
return false
}
In the worst case, we will be performing a single scan of the array or accessing each array element only once. So time complexity = O(n). Space complexity = O(1) i.e we are using constant extra space.
Here is another analogy of the solution. Suppose two people are climbing from the left and right end separately. If there is a valid mountain, their first peak point will be the same. In other words, both will meet at the only peak point in mountain array. Otherwise, if there is no valid mountain, their first peak point will be different. (Think!)
Now using loop, we start climbing from the left end and reach the peak.
while (left < n - 1 && X[left] < X[left + 1])
left = left + 1
Using the loop, we start climbing from the right end and reach the peak.
while (right > 0 && X[right - 1] > X[right])
right = right - 1
boolean validMountain(int X[], int n)
{
left = 0, right = n - 1
while (left < n - 1 && X[left] < X[left + 1])
left = left + 1
while (right > 0 && X[right - 1] > X[right])
right = right - 1
if(left > 0 && left == right && right < n - 1)
return true
else
return false
}
In the worst case, we will be traversing each element of the array only once, so time complexity = O(n). Space complexity = O(1) i.e we are using constant extra space.
Important note: We recommend learners transform the above pseudocodes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Enjoy programming!
Here is a code snippet where we are tracking the down movement using a boolean variable downMove. Is this solution correct?
boolean validMountain(int X[], int n)
{
if (n <= 2 || X[0] > X[1])
return false
boolean downMove = false
for (int i = 2; i < n; i = i + 1)
{
if (X[i] < X[i - 1])
downMove = true
else if (X[i] == X[i - 1] || downMove)
return false
}
return downMove
}
Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.