# Longest Mountain in Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-mountain-in-array)
Canonical: https://scaleengineer.com/dsa/problems/longest-mountain-in-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [SoFi](https://scaleengineer.com/companies/sofi), [Databricks](https://scaleengineer.com/companies/databricks), [Faire](https://scaleengineer.com/companies/faire)
---
## Problem
You may recall that an array `arr` is a **mountain array** if and only if:

* `arr.length >= 3`
* There exists some index `i` (**0-indexed**) with `0 < i < arr.length - 1` such that:  
  * `arr[0] < arr[1] < ... < arr[i - 1] < arr[i]`
  * `arr[i] > arr[i + 1] > ... > arr[arr.length - 1]`

Given an integer array `arr`, return _the length of the longest subarray, which is a mountain_. Return `0` if there is no mountain subarray.

**Example 1:**

**Input:** arr = [2,1,4,7,3,2,5]
**Output:** 5
**Explanation:** The largest mountain is [1,4,7,3,2] which has length 5.

**Example 2:**

**Input:** arr = [2,2,2]
**Output:** 0
**Explanation:** There is no mountain.

**Constraints:**

* `1 <= arr.length <= 104`
* `0 <= arr[i] <= 104`

**Follow up:**

* Can you solve it using only one pass?
* Can you solve it in `O(1)` space?

# Approaches
## Brute Force by Identifying Peaks
This approach iterates through every possible peak in the array. A peak is an element that is greater than its immediate neighbors. For each potential peak found, we expand outwards to the left and right to determine the full extent of the mountain.
**Time:** O(N^2). The outer loop runs `N` times. In the worst-case scenario (a long, gentle slope), the inner `while` loops for expansion could also run up to `N` times for each peak. · **Space:** O(1). We only use a few variables to store indices and the max length.
**Pros:** Conceptually simple and easy to implement.; It correctly identifies all mountains by checking every possible peak.
**Cons:** Inefficient due to its quadratic time complexity.; It may be too slow for large input arrays and could result in a "Time Limit Exceeded" error on some platforms.; It re-scans parts of the array multiple times.
### Explanation
The core idea is that any mountain subarray must have a peak. A peak `arr[i]` is defined by the condition `arr[i-1] < arr[i] > arr[i+1]`. We can iterate through the array from the second element to the second-to-last element (`i` from 1 to `n-2`). At each index `i`, we check if `arr[i]` can be a peak. If it is, we treat it as the center of a mountain and expand in both directions. We use one pointer, `l`, starting from `i`, moving leftwards as long as the array is strictly increasing (`arr[l-1] < arr[l]`). We use another pointer, `r`, starting from `i`, moving rightwards as long as the array is strictly decreasing (`arr[r] > arr[r+1]`). The length of the mountain found is `r - l + 1`. We keep track of the maximum length found across all possible peaks. This process is repeated for every potential peak in the array.

```java
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }
        int maxLength = 0;
        for (int i = 1; i < n - 1; i++) {
            // Check if i is a peak
            if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
                int left = i - 1;
                int right = i + 1;
                // Expand to the left
                while (left > 0 && arr[left - 1] < arr[left]) {
                    left--;
                }
                // Expand to the right
                while (right < n - 1 && arr[right] > arr[right + 1]) {
                    right++;
                }
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through the array with an index `i` from `1` to `arr.length - 2`.
- At each `i`, check if `arr[i]` is a peak: `arr[i-1] < arr[i] && arr[i] > arr[i+1]`.
- If it is a peak:
    - Initialize `left = i - 1` and `right = i + 1`.
    - Expand to the left: `while (left > 0 && arr[left - 1] < arr[left]) { left--; }`.
    - Expand to the right: `while (right < arr.length - 1 && arr[right] > arr[right + 1]) { right++; }`.
    - Calculate the length of the current mountain: `currentLength = right - left + 1`.
    - Update `maxLength = max(maxLength, currentLength)`.
- After the loop, return `maxLength`.

## Dynamic Programming Approach
This approach uses dynamic programming to solve the problem in linear time. We use two auxiliary arrays, `up` and `down`, to precompute the lengths of increasing subarrays ending at each index and decreasing subarrays starting at each index, respectively.
**Time:** O(N). We perform three separate passes over the array, each taking `O(N)` time. The total time complexity is `O(N) + O(N) + O(N) = O(N)`. · **Space:** O(N). We use two additional arrays, `up` and `down`, each of size `N`.
**Pros:** Very efficient time complexity.; The logic is straightforward, breaking the problem down into smaller subproblems.
**Cons:** Requires extra space proportional to the input size, which might be a concern for memory-constrained environments.; Does not meet the follow-up requirement of `O(1)` space.
### Explanation
We create two arrays, `up` and `down`, of the same size as the input array `arr`. `up[i]` will store the length of the strictly increasing subarray ending at index `i`, and `down[i]` will store the length of the strictly decreasing subarray starting at index `i`. We populate the `up` array with a forward pass and the `down` array with a backward pass. After populating both arrays, we iterate through the array one more time. For each index `i`, if it's a peak of a mountain (`up[i] > 0` and `down[i] > 0`), the length of the mountain is `up[i] + down[i] + 1`. We find the maximum of these lengths over all possible peaks `i`.

```java
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }
        
        int[] up = new int[n];
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up[i] = up[i - 1] + 1;
            }
        }
        
        int[] down = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                down[i] = down[i + 1] + 1;
            }
        }
        
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            if (up[i] > 0 && down[i] > 0) {
                maxLength = Math.max(maxLength, up[i] + down[i] + 1);
            }
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Get the length `n` of the array. If `n < 3`, return 0.
- Create two integer arrays, `up` and `down`, of size `n`.
- Populate `up`: `up[i]` will store the length of the strictly increasing part of a mountain ending at `i`. Iterate from `i = 1` to `n-1`. If `arr[i] > arr[i-1]`, set `up[i] = up[i-1] + 1`.
- Populate `down`: `down[i]` will store the length of the strictly decreasing part of a mountain starting at `i`. Iterate from `i = n-2` down to `0`. If `arr[i] > arr[i+1]`, set `down[i] = down[i+1] + 1`.
- Initialize `maxLength = 0`.
- Iterate from `i = 0` to `n-1`.
- If `up[i] > 0` and `down[i] > 0`, it means `arr[i]` is a peak of a valid mountain.
- Calculate the length: `currentLength = up[i] + down[i] + 1`.
- Update `maxLength = max(maxLength, currentLength)`.
- Return `maxLength`.

## Optimal Single Pass Approach
This is the most efficient approach, solving the problem in a single pass through the array and using constant extra space. It works by identifying the start, peak, and end of each mountain in one go, treating the array as a sequence of upslopes and downslopes.
**Time:** O(N). Although there are nested loops, the main pointer `i` is never reset. It continuously moves from the beginning to the end of the array. Each element is visited at most a constant number of times. · **Space:** O(1). We only use a few variables to keep track of indices and the maximum length, independent of the input size.
**Pros:** Optimal time complexity `O(N)`.; Optimal space complexity `O(1)`, satisfying the follow-up question.; Highly efficient as it processes the array in a single pass.
**Cons:** The logic can be slightly more complex to reason about compared to the DP approach due to the pointer manipulation.
### Explanation
We iterate through the array using a single pointer `i`. The pointer `i` will effectively traverse the start, peak, and end of each mountain sequentially. The algorithm can be thought of as a state machine: find an uphill slope, then find a downhill slope. If both are found, we have a mountain. The key insight is that after processing a mountain that ends at index `end`, the search for the next mountain can begin at `end`, ensuring each element is visited only a constant number of times.

```java
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int maxLength = 0;
        int i = 0;
        
        while (i < n) {
            int base = i;
            
            // Walk up: find the start of an uphill slope
            if (i + 1 < n && arr[i] < arr[i + 1]) {
                while (i + 1 < n && arr[i] < arr[i + 1]) {
                    i++;
                }
                
                // Check if we found a peak followed by a downhill
                if (i + 1 < n && arr[i] > arr[i + 1]) {
                    // Walk down
                    while (i + 1 < n && arr[i] > arr[i + 1]) {
                        i++;
                    }
                    // Update maxLength for the valid mountain found
                    maxLength = Math.max(maxLength, i - base + 1);
                }
            }
            
            // If we didn't find a mountain starting at base, or after processing one,
            // move to the next position. This handles plateaus and single slopes.
            if (i == base) {
                i++;
            }
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0` and a pointer `i = 0`.
- Loop while `i` is less than the array length.
- Let `base = i`.
- Find an uphill slope: check if `i+1` is in bounds and `arr[i] < arr[i+1]`. If so, advance `i` as long as this condition holds.
- After the uphill walk, `i` is at a potential peak. Check if a downhill slope exists: `i+1` is in bounds and `arr[i] > arr[i+1]`.
- If an uphill slope was found (`i > base`) and a downhill slope exists, then walk down by advancing `i` as long as the downhill condition holds.
- After the downhill walk, a valid mountain from `base` to `i` has been found. Update `maxLength` with `i - base + 1`.
- If no mountain was found starting at `base` (e.g., it was flat or only went up), simply advance `i` by one to check the next position. This prevents an infinite loop.
- Continue the process until the entire array is scanned.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestMountain(int[] arr) {
    int n = arr.length;
    int ans = 0;
    for (int l = 0, r = 0; l + 2 < n; l = r) {
      r = l + 1;
      if (arr[l] < arr[r]) {
        while (r + 1 < n && arr[r] < arr[r + 1]) {
          ++r;
        }
        if (r + 1 < n && arr[r] > arr[r + 1]) {
          while (r + 1 < n && arr[r] > arr[r + 1]) {
            ++r;
          }
          ans = Math.max(ans, r - l + 1);
        } else {
          ++r;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestMountain(vector<int> &arr) {
    int n = arr.size();
    int ans = 0;
    for (int l = 0, r = 0; l + 2 < n; l = r) {
      r = l + 1;
      if (arr[l] < arr[r]) {
        while (r + 1 < n && arr[r] < arr[r + 1]) {
          ++r;
        }
        if (r + 1 < n && arr[r] > arr[r + 1]) {
          while (r + 1 < n && arr[r] > arr[r + 1]) {
            ++r;
          }
          ans = max(ans, r - l + 1);
        } else {
          ++r;
        }
      }
    }
    return ans;
  }
};

```

### Python

```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

```