Difficulty: Easy, Asked-in: Google, Amazon
Key takeaway
Given an array X of n integers, write a program to check if the 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, the 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 at least 15 or 30 minutes. Enjoy problem-solving!
Input: X[] = [5, 2, 1, 4], Output: false
Input: X[] = [5, 8, 8], Output: false
Input: X[] = [1, 2, 6, 5, 3], Output: true
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
bool validMountain(int X[], int n)
{
int climb = 0;
// Find the peak of the mountain
while (climb < n - 1 && X[climb] < X[climb + 1])
climb = climb + 1;
// Return false if the peak is at the beginning or end
if (climb == 0 || climb == n - 1)
return false;
// Traverse down the mountain
while (climb < n - 1 && X[climb] > X[climb + 1])
climb = climb + 1;
// Return true if the end of the mountain is reached
if (climb == n - 1)
return true;
else
return false;
}
def validMountain(X, n):
climb = 0
while climb < n - 1 and X[climb] < X[climb + 1]:
climb = climb + 1
if climb == 0 or climb == n-1:
return False
while climb < n - 1 and 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
bool validMountain(int X[], int n)
{
int left = 0, right = n - 1;
// Traverse up the mountain from left side
while (left < n - 1 && X[left] < X[left + 1])
left = left + 1;
// Traverse up the mountain from right side
while (right > 0 && X[right - 1] > X[right])
right = right - 1;
// Check if both pointer meet at the same peak
if (left > 0 && left == right && right < n - 1)
return true;
else
return false;
}
def validMountain(X, n):
left = 0
right = n - 1
while left < n - 1 and X[left] < X[left + 1]:
left = left + 1
while right > 0 and X[right - 1] > X[right]:
right = right - 1
if left > 0 and left == right and 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 and verify all the test cases. Enjoy programming!
Here is a pseudocode 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!