Scale Engineer

Longest Mountain in Array

Med
#0799Time: 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`.3 companies
Patterns
Two PointersDynamic ProgrammingEnumeration
Data structures
Array
Companies
SoFiDatabricksFaire

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem