Leetcode 845. Longest Mountain in Array
Problem Description
Given an array of integers, we are to return the length of the longest contiguous subarray that is described as a mountain. A subarray B is considered a mountain if:
- Length of B is greater than or equal to 3.
- There exists some
0 < i < B.length - 1
such thatB[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
. This means that, for some indexi
inB
, all elements beforei
are less thanB[i]
and all elements afteri
are less thanB[i]
.
The task is to find the length of the longest mountain in the array. If no such mountain exists, we return 0.
For example, consider the array [2,1,4,7,3,2,5]
. The largest mountain is [1,4,7,3,2]
which has a length of 5.
Solution
To solve this problem, we initialize variable ans
to keep track of the length of the longest mountain. Starting from the beginning of the array, we check if the current element is equal to the next one. If it is, we simply increment the index and move to the next element.
We then initialize two variables, increasing
and decreasing
. These are used to keep track of the number of increasing and decreasing elements respectively. As we traverse the array, we increment increasing
if the current element is less than the next and increment decreasing
if the current element is greater than the next.
After traversing the array, if increasing
and decreasing
are both greater than 0, it means that we have found a mountain. We then compare the length of the mountain to ans
and update ans
if the length of the mountain is greater than ans
.
Finally, we return ans
which is the length of the longest mountain.
C++ Solution
1
2cpp
3#include <vector>
4
5class Solution {
6public:
7 int longestMountain(std::vector<int>& arr) {
8 int ans = 0;
9
10 for (int i = 0; i + 1 < arr.size();) {
11 // Ignore duplicate numbers.
12 while (i + 1 < arr.size() && arr[i] == arr[i + 1]) {
13 ++i;
14 }
15
16 // Count the number of increasing elements.
17 int increasing = 0;
18 while (i + 1 < arr.size() && arr[i] < arr[i + 1]) {
19 ++increasing;
20 ++i;
21 }
22
23 // Count the number of decreasing elements.
24 int decreasing = 0;
25 while (i + 1 < arr.size() && arr[i] > arr[i + 1]) {
26 ++decreasing;
27 ++i;
28 }
29
30 // Check if there is a mountain and update ans.
31 if (increasing > 0 && decreasing > 0) {
32 ans = std::max(ans, increasing + decreasing + 1);
33 }
34 }
35
36 return ans;
37 }
38};
Python Solution
1 2python 3class Solution: 4 def longestMountain(self, arr): 5 ans = 0 6 i = 0 7 8 while i + 1 < len(arr): 9 if arr[i] == arr[i + 1]: 10 i += 1 11 continue 12 13 increasing = 0 14 while i + 1 < len(arr) and arr[i] < arr[i + 1]: 15 increasing += 1 16 i += 1 17 18 decreasing = 0 19 while i + 1 < len(arr) and arr[i] > arr[i + 1]: 20 decreasing += 1 21 i += 1 22 23 if increasing > 0 and decreasing > 0: 24 ans = max(ans, increasing + decreasing + 1) 25 26 return ans
Java Solution
1 2java 3class Solution { 4 public int longestMountain(int[] arr) { 5 int ans = 0; 6 int i = 0; 7 8 while (i + 1 < arr.length) { 9 while (i + 1 < arr.length && arr[i] == arr[i + 1]) { 10 i++; 11 } 12 13 int increasing = 0; 14 while (i + 1 < arr.length && arr[i] < arr[i + 1]) { 15 increasing++; 16 i++; 17 } 18 19 int decreasing = 0; 20 while (i + 1 < arr.length && arr[i] > arr[i + 1]) { 21 decreasing++; 22 i++; 23 } 24 25 if (increasing > 0 && decreasing > 0) { 26 ans = Math.max(ans, increasing + decreasing + 1); 27 } 28 } 29 30 return ans; 31 } 32}
JavaScript Solution
1 2js 3class Solution { 4 longestMountain(arr) { 5 let ans = 0; 6 let i = 0; 7 8 while (i + 1 < arr.length) { 9 while (i + 1 < arr.length && arr[i] == arr[i + 1]) { 10 i++; 11 } 12 13 let increasing = 0; 14 while (i + 1 < arr.length && arr[i] < arr[i + 1]) { 15 increasing++; 16 i++; 17 } 18 19 let decreasing = 0; 20 while (i + 1 < arr.length && arr[i] > arr[i + 1]) { 21 decreasing++; 22 i++; 23 } 24 25 if (increasing > 0 && decreasing > 0) { 26 ans = Math.max(ans, increasing + decreasing + 1); 27 } 28 } 29 30 return ans; 31 } 32};
C# Solution
1 2csharp 3class Solution { 4 public int LongestMountain(int[] arr) { 5 int ans = 0; 6 int i = 0; 7 8 while(i + 1 < arr.Length) { 9 while (i + 1 < arr.Length && arr[i] == arr[i + 1]) { 10 i++; 11 } 12 13 int increasing = 0; 14 while (i + 1 < arr.Length && arr[i] < arr[i + 1]) { 15 increasing++; 16 i++; 17 } 18 19 int decreasing = 0; 20 while (i + 1 < arr.Length && arr[i] > arr[i + 1]) { 21 decreasing++; 22 i++; 23 } 24 25 if (increasing > 0 && decreasing > 0) { 26 ans = Math.Max(ans, increasing + decreasing + 1); 27 } 28 } 29 30 return ans; 31 } 32}
In conclusion, this problem can be solved by keeping track of the increasing and decreasing elements in the array. We traverse the entire array only once, hence the time complexity of the solution is O(n), where n is the length of the array.
Our approach relies on counting the number of continuously increasing and decreasing elements and checking if they form a mountain. When we find a mountain, we compare its length to the length of the longest mountain found so far, and update it if it's longer.
So far we have covered solutions in C++, Python, Java, JavaScript and C#. Each solution implements the same logic, although the syntax differs from language to language. With a good understanding of the arrays and control flow statements in each of these programming languages, one should be able to implement this solution with ease.
Remember that while solving such problems, it's essential that the solution not just return the correct output but is also efficient. In many real-world problems, time and space efficiency plays a crucial role. Here, using a simple two-pointer technique, we were able to achieve an optimal and very efficient solution.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.