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.
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, 4, 2], Output: true
Solution Approach 1: Traversing from left to right
Solution Approach 2: Traversing from opposite ends
Solution Idea and Steps
If there is a mountain then we first move up from left to the peak and then move down from peak to the right. So the basic idea would be : scan the array from the left and check the strictly increasing and then decreasing order of elements.
By end of the loop, if the peak is present at first or the last element i.e. climb = 0 or climb = n - 1, then we return false. In other words, the peak can’t be the first or last element in the mountain.
int climb = 0
while (climb < n - 1 && X[climb] < X[climb + 1])
climb = climb + 1
if (climb == 0 || climb == n - 1)
return false
If the peak is present at some middle element then similarly, we run a loop from that position to check the strictly decreasing order or elements. If we reach the end, the 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
Solution Pseudocode
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
}
Solution Analysis
In the worst case, we are performing a single scan of the array i.e we are accessing each element of the array only once. Time complexity = O(n). Space complexity = O(1) i.e no extra space is used.
Solution Idea and Steps
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, then their first peak point will be the same. In other words, both will meet at the only peak point in the mountain array. Otherwise, if there is no valid mountain, then their first peak point would be different. (Think!)
Using the loop, climb from the left end and reach the peak.
while (left < n - 1 && X[left] < X[left + 1])
left = left + 1
Using the loop, climb the right end and reach the peak.
while (right > 0 && X[right - 1] > X[right])
right = right - 1
Solution Pseudocode
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
}
Solution Analysis
In the worst case, we are traversing each element of the array only once. 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 down_move. Is this solution correct?
boolean validMountain(int X[], int n)
{
if (n <= 2 || X[0] > X[1])
return false
boolean down_move = false
for (int i = 2; i < n; i = i + 1)
{
if (X[i] < X[i - 1])
down_move = true
else if (X[i] == X[i - 1] || down_move)
return false
}
return down_move
}
Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!
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!
Given an array of n non-negative integers height[n], where each represents a point at coordinate (i, height[i]). n vertical lines are drawn such that the two endpoints of line i is at (i, height[i]) and (i, 0). Write a program to find two lines, which together with the x-axis forms a container, such that the container contains the most water.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!