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:

1. Length of B is greater than or equal to 3.
2. There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]. This means that, for some index i in B, all elements before i are less than B[i] and all elements after i are less than B[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.