845. Longest Mountain in Array
Asked at Databricks, TikTok
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
2
Problem
You are given an integer array arr. A mountain is a contiguous subarray that first goes strictly up, then strictly down. It must have at least 3 elements, so it needs at least one step up and at least one step down.
More precisely, a subarray is a mountain if there is a peak index i inside it such that all values strictly increase up to i, and then strictly decrease after i. Equal neighbours are not allowed on either side, so a flat part breaks the mountain.
Return the length of the longest mountain subarray. If no mountain exists, return 0.
Find the longest up-then-down run
Constraints
- ●
1 <= arr.length <= 10^4 - ●
0 <= arr[i] <= 10^4
Examples
arr = [2,1,4,7,3,2,5]5arr = [2,2,2]0Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| TikTok | Medium | View all TikTok 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.
One pass with up and down counters
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Mountain in Array?
Longest Mountain in Array is asked at Databricks, TikTok. 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