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.
Examples
Input: X[] = [5, 2, 1, 4], Output: false
Input: X[] = [5, 8, 8], Output: false
Input: X[] = [1, 2, 4, 2], Output: true
Important note: Before moving to the solutions, we recommend learners solve this problem. If solved, then well done! We would like to hear your ideas in the comment. Otherwise no problem, this is an opportunity to learn a new pattern in problem-solving!
Solution 1: Traversing from left to right end
Solution 2: Traversing from both 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
Time and space complexity 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
Time and space complexity 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 no extra space is used.
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!
Enjoy learning, Enjoy coding, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.