Problem: Longest Mountain in Array

The problem asks to find the length of the longest mountain subarray within a given integer array. A mountain array is defined as an array with at least three elements where:

1. There's a peak element arr[i] such that 0 < i < arr.length - 1.
2. Elements strictly increase before the peak: arr[0] < arr[1] < ... < arr[i].
3. Elements strictly decrease after the peak: arr[i] > arr[i+1] > ... > arr[arr.length - 1].

Solution Approaches and Code Explanations

Two solutions are presented: one using dynamic programming and another using a single pass.

Solution 1: Dynamic Programming

This approach uses two arrays, f and g, to store the lengths of the increasing and decreasing subarrays ending at each index, respectively.

Algorithm:

1. Initialize f and g with all 1s (each element is a subarray of length 1).
2. Iterate through the array from left to right to compute f. If arr[i] > arr[i-1], it extends the increasing subarray, so f[i] = f[i-1] + 1.
3. Iterate through the array from right to left to compute g. If arr[i] > arr[i+1], it extends the decreasing subarray, so g[i] = g[i+1] + 1.
4. For each index i, if both f[i] > 1 and g[i] > 1, it means there's a mountain at index i. The length of this mountain is f[i] + g[i] - 1 (avoid double-counting the peak). Update the maximum length ans.
5. Return ans.

Time Complexity: O(N), where N is the length of the array. We iterate through the array twice. Space Complexity: O(N) to store f and g arrays.

Code (Python):

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                f[i] = f[i - 1] + 1
        ans = 0
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                g[i] = g[i + 1] + 1
                if f[i] > 1:
                    ans = max(ans, f[i] + g[i] - 1)
        return ans
 

Similar code implementations exist for Java, C++, and Go in the original response.

Solution 2: Single Pass

This approach iterates through the array only once. It identifies potential mountain peaks and extends the mountain length from the peak in both directions.

Algorithm:

1. Initialize ans (maximum mountain length) and l (current index).
2. Iterate while l + 2 < n.
3. If arr[l] < arr[l+1], we might have an increasing sequence, so we find the end of the increasing sequence (r).
4. If r < n - 1 and arr[r] > arr[r+1], we have a decreasing sequence after the increasing one (a mountain). Extend r to find the end of the decreasing sequence. Update ans.
5. Otherwise, we skip to the next potential mountain start (l = r).

Time Complexity: O(N). We iterate through the array at most once. Space Complexity: O(1). We use only a few constant variables.

Code (Python):

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = l = 0
        while l + 2 < n:
            r = l + 1
            if arr[l] < arr[r]:
                while r + 1 < n and arr[r] < arr[r + 1]:
                    r += 1
                if r < n - 1 and arr[r] > arr[r + 1]:
                    while r < n - 1 and arr[r] > arr[r + 1]:
                        r += 1
                    ans = max(ans, r - l + 1)
                else:
                    r += 1
            l = r
        return ans

Again, similar code implementations exist for Java, C++, and Go in the original response. Both solutions achieve the same result, but the second one is more efficient in terms of space complexity. Choose the solution that best suits your needs and coding style.