Skip to main content
Talentd

Longest Mountain in Array - Solution & Explanation

MediumArrayTwo PointersDynamic ProgrammingEnumeration15 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

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?

Approach Overview

Problem Overview: You are given an integer array and need the length of the longest mountain. A mountain is a subarray where values strictly increase to a peak and then strictly decrease. The subarray must contain at least three elements and the peak cannot be at the ends.

The challenge is identifying valid peaks while ensuring the left side strictly rises and the right side strictly falls. Efficient solutions avoid recomputing slopes for every position and instead track increasing and decreasing segments using linear scans. This problem mainly relies on array traversal patterns from Array problems combined with pointer movement techniques from Two Pointers.

Approach 1: Two-Pass Approach with Peak Detection (O(n) time, O(n) space)

This approach precomputes how long the array increases and decreases at every index. First pass from left to right builds an up[] array where up[i] stores the length of the increasing slope ending at i. Second pass from right to left builds a down[] array where down[i] stores the length of the decreasing slope starting at i. A valid mountain peak exists where both values are greater than zero. The total mountain length becomes up[i] + down[i] + 1. Iterate through all indices and track the maximum.

This method is easy to reason about because each direction is handled independently. The tradeoff is extra memory for two arrays, but the logic stays simple and deterministic. The idea resembles prefix-style preprocessing seen in Dynamic Programming problems where partial results are reused.

Approach 2: Single-Pass Gradient Tracking (O(n) time, O(1) space)

This approach scans the array once while tracking the current uphill and downhill lengths. When the sequence is increasing, increment the up counter. When it switches to decreasing, increment the down. A valid mountain appears only if both counters are positive. If the slope resets (equal values or a new increasing segment after decreasing), reset the counters accordingly.

During each step, update the answer when both up > 0 and down > 0. The length of the current mountain is up + down + 1. This solution effectively performs inline Enumeration of slope segments while maintaining only constant state. Because it avoids auxiliary arrays, it is memory efficient and performs a clean linear traversal.

Recommended for interviews: Interviewers usually expect the single-pass gradient solution. It demonstrates that you recognize the slope pattern and can maintain state while scanning once. The two-pass approach still shows strong understanding of the problem structure and is often a stepping stone toward the optimal O(1) space solution.

Approach 1: Two-Pass Approach with Peak Detection

This approach involves scanning the array to find all the peaks and then measuring the length of a mountain centered at each peak. We use two traversals: one forward scan to detect peaks and another scan to calculate maximum width of the mountains.

The C solution iterates through the array looking for peaks (where arr[i] is greater than its neighbors). Upon finding a peak, it expands outwards to calculate the total length of the mountain by decrementing and incrementing indices as long as the mountain shape holds. The maxLen keeps track of the longest mountain found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n) as each element is processed at most twice. Space complexity is O(1) since we use only a few extra variables.

Try this approach in the editor →

Approach 2: Single-Pass Approach with Gradient Tracking

This approach uses a single pass through the array to maintain both ascent and descent counts, swapping them at every ascent reset. A separate check is performed to ensure valid peaks for mountain length calculations.

This C implementation leverages variable ascent to track climbing phase and descent for descent. A valid mountain forms when both ascent and descent qualities exceed zero. The inner loop skips flat sections to align with mountain criteria.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pass Approach with Peak Detection

Time complexity is O(n) as each element is processed at most twice. Space complexity is O(1) since we use only a few extra variables.

Single-Pass Approach with Gradient Tracking

Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass Peak DetectionO(n)O(n)Best when clarity matters; easy to debug using explicit increasing and decreasing arrays
Single-Pass Gradient TrackingO(n)O(1)Preferred in interviews and production due to constant memory and one traversal

Video Solution

Longest Mountain in Array Leetcode 845 || Medium • Code with Alisha • 16,724 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Mountain in Array easy or hard?
Longest Mountain in Array is considered a medium difficulty problem. The logic becomes straightforward once you recognize the increasing-then-decreasing slope pattern, but handling resets and edge cases correctly can make the implementation tricky.
Longest Mountain in Array Python/Java solution
Both Python and Java implementations typically follow the single-pass slope tracking pattern. Iterate through the array, update increasing and decreasing counters based on comparisons with the previous element, and update the maximum mountain length when both counters are positive.
How to solve Longest Mountain in Array in O(n)?
Traverse the array while tracking the length of increasing and decreasing slopes. Increase the uphill counter when values rise and the downhill counter when values fall. A valid mountain occurs when both counters are positive, and the length becomes up + down + 1. Reset counters when the slope pattern breaks.
What is the best approach for Longest Mountain in Array?
The best approach is the single-pass gradient tracking method with O(n) time and O(1) space. It scans the array once while counting increasing and decreasing slopes. When both counters are positive, a valid mountain exists and the length can be computed as up + down + 1. This avoids extra arrays and is the approach most interviewers expect.
Is Longest Mountain in Array asked at Google/Amazon/Meta?
Longest Mountain in Array is a common medium-level interview problem that appears in coding rounds at companies like Google, Amazon, and Meta. It tests pattern recognition in arrays, linear scanning techniques, and the ability to manage state transitions efficiently.
What data structure is used in Longest Mountain in Array?
The problem primarily uses arrays and simple counters. Some solutions use auxiliary arrays to track increasing and decreasing slopes, while optimized solutions maintain only two integer counters during a single pass through the input array.
What is the time complexity of Longest Mountain in Array?
The optimal solutions run in O(n) time where n is the length of the array. Each element is processed at most once during a linear scan. Some implementations use two passes with auxiliary arrays, while the most optimized version completes everything in a single pass.

Ready to solve this problem?

Practice Longest Mountain in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Good Days to Rob the Bank

Next

Minimum Number of Removals to Make Mountain Array