Longest Mountain in Array

MEDIUM

Description

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 <= 10⁴
0 <= arr[i] <= 10⁴

Follow up:

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

Approaches

Checkout 3 different approaches to solve Longest Mountain in Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(N). We use two additional arrays, `up` and `down`, each of size `N`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Longest Mountain in Array. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Longest Mountain in Array

Patterns:

Two PointersDynamic ProgrammingEnumeration

Data Structures:

Array

Companies:

SoFi |Databricks |Faire |