Here’s the problem statement:
Given an array of integers, find the length of the longest mountain in the array.
Mountain here represents a subarray where the values of the constituent integers first follow a strictly increasing and then a strictly decreasing order.
For example:
The array: 10, 12, 40, 30, 20, -1, 5, 6, 1
Output: 6 where the mountain is [10, 12, 40, 30, 20, -1]
Let’s dive into the solution:
Approach 1:
A simple way to work this problem is to find the top of a possible mountain (i.e. the highest pt. in the mountain whose value is greater than both its neighbours) and then move towards left to the start of the mountain (i.e. to the point at which the mountain’s ascent starts) and towards the right to the end of the mountain (i.e. to the point at which the mountain’s descent ends) while keeping a count of the number of indices in the mountain.
And then eventually return the maximum length of all mountains possible.
For instance: In the given array, 40 is a top since 40>12 and 40>30,
moving left of 40 towards the mt.’s left-most end, we run through: [12, 10],
and moving right of 40 towards the mt.’s right-most end, we run through: [30, 20, -1]
So the complete mt. range is: [12, 10, 40, 30, 20, -1] of length 6.
Similarly, 6 is a top as 6>5 and 6<1,
moving to the left of 6 towards the start of the mt.: [5, -1],
and moving to the right of 6 towards the end of the mt.: [6, 1]
So the complete mt. range is: [-1, 5, 6, 1] of length 4
Therefore the length of the longest mt. in the given array is 6
Now, to find a top we loop over the elements in the array and look for an element array[i] where array[i]>array[i-1] and array[i]>array[i+1]. Once we’ve found a top, we can move left/right to the mt.’s ends.
Time complexity: We visit every element atleast once while checking if it could form a top or while going down a descent. And we visit the values in the ascent of the mts. 1 more time while moving to the left of the mt. tops.
Therefore any element in the array is at max visited 2 times. So the time complexity is O(N)
Space complexity: O(1)
Here’s the code for this solution in Java:
public int longestMountain(int[] array) {
int mtLength, maxLength, i, j;
mtLength = maxLength = j = 0;
i = 1;
while((i+1)<array.length) { //check if any of the (1th to 2nd-last) elements is a top
//note that the 0th and the last element cannot be mt. tops because they do not have any elements for ascent on the left/descent on their right sides respectively
if(array[i]>array[i-1] && array[i]>array[i+1]) {//we've found a mt. top
j = i-1; mtLength = 1;//count 1 for the peak
while(j>=0 && array[j]<array[j+1]) {//move towards the left of the top to the start of the ascent
ct++; j--;
}
j = i+1;
while(j<array.length && array[j]<array[j-1]) {//move towards the right of the top to the end of the descent
ct++; j++;
}//when this loop breaks out then j points to the element immediately after the end of the descent
maxLength = Math.max(maxLength, mtLength);
i = j;//since the elements lying between indices i and j form a part of the descent of this mt. so there cannot be a mt. top there and so skip them
}
else//if this isn't a mt. top, then just increment to check if the next element is a mt. top
i++;
}
return maxLength;
}
Approach 2:
Another way to work the problem is:
Loop over the array elements and check if current value could be the start of the ascent of any mt. i.e. if array[i]<array[i+1], if so, the save this beginningIndex, then move to the right all the way to the top (i.e. while array[i]<array[i+1]) and then all the way down the descent till the mt.’s descent’s end (i.e. while array[i]>array[i+1]).
The current mt.’s length = current index – beginningIndex.
And then eventually return the maximum length of all mountains possible.
Time complexity: We visit every element exactly once so the time complexity is O(N)
Space complexity: O(1)
Here’s the code for this solution in Java:
public int longestMountain(int[] array) {
int maxLength, beginingIndex, i, j;
maxLength = beginingIndex = j = 0;
i = 0;
while((i+1)<array.length) { //go in only as long as we're not at the last element because a mt.'s ascent can't start at the last element
if((i+1)<array.length && array[i]<array[i+1]) {//if this is probably the beginning of a mt.'s ascent
beginingIndex = i;
while((i+1)<array.length && array[i]<array[i+1]) {//go up the ascent all the way to the top
i++;
}//when this first while loop breaks off then i points to the top of the possible mt.
if((i+1)<array.length && array[i]>array[i+1]) {//if this is probably the beginning of the descent
while((i+1)<array.length && array[i]>array[i+1]) {//go all the way down the descent till the mt.'s descent's end
i++;
}//when this second while loop breaks off then i points to the last elem. in the descent
maxLength = Math.max(maxLength, i-beginingIndex+1);
}
}
else { //if this is not the start of the ascent (it could be a flat area i.e. adjacent elements having same value or a part of a descent with no coreesponding ascent) then just increment to check the next element
i++;
}
}
return maxLength;
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂
The Code Scribbbler 