Longest Mountain in Array
Asked at Databricks
Problem
You may recall that an array arr is a mountain array if it has at least 3 elements, and there exists some index i such that arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[arr.length - 1]. Given an integer array arr, return the length of the longest mountain in arr. This problem tests two-pointer technique and enumeration of peaks.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | MEDIUM | View all Databricks questions → |
How to Think About It
Enumerate every index as a potential peak and expand left and right
Compute left[i]: length of strictly increasing sequence ending at i
Compute right[i]: length of strictly decreasing sequence starting at i
A mountain at index i has length left[i] + right[i] - 1 if both sides exist
Optimal single-pass: track up and down counts, reset when pattern breaks
Optimal Approach
Use a single pass with two pointers tracking the length of the current ascent and descent. Iterate through the array, counting consecutive increases (up) and decreases (down). When arr[i] > arr[i-1], increment up and reset down. When arr[i] < arr[i-1], increment down. If both up > 0 and down > 0, a valid mountain exists with length up + down + 1. Track the maximum across all valid mountains. When arr[i] == arr[i-1], the mountain is broken so reset both counters. This runs in O(n) time and O(1) space.
What Trips People Up in Real Interviews
Clarify that mountains must have at least 3 elements (up and down on both sides)
Peak cannot be at index 0 or last index since you need both sides
Two-pass DP approach is clean: one pass for increasing lengths, one for decreasing
Single-pass two-pointer is more elegant but harder to explain under pressure
Edge case: array of all equal values has no mountains
Solution Code
def longestMountain(arr):
n = len(arr)
res = 0
up = 0
down = 0
for i in range(1, n):
if arr[i] > arr[i - 1]:
if down > 0:
up = 0
down = 0
up += 1
elif arr[i] < arr[i - 1]:
down += 1
if up > 0:
res = max(res, up + down + 1)
else:
up = 0
down = 0
return resFrequently Asked Questions
What is the Longest Mountain in Array problem?
You may recall that an array arr is a mountain array if it has at least 3 elements, and there exists some index i such that arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[arr.length - 1]. Given an integer array arr, return the length of the longest mountain in arr. This problem tests two-pointer technique and enumeration of peaks.
How do you solve Longest Mountain in Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Mountain in Array?
Longest Mountain in Array is asked at Databricks. It is a medium difficulty problem.
What are common mistakes on Longest Mountain in Array?
- Clarify that mountains must have at least 3 elements (up and down on both sides)
- Peak cannot be at index 0 or last index since you need both sides
- Two-pass DP approach is clean: one pass for increasing lengths, one for decreasing
- Single-pass two-pointer is more elegant but harder to explain under pressure
- Edge case: array of all equal values has no mountains