Use a state transition dynamic programming approach with two pointers to track increasing and decreasing sequences. Iterate through the array, expanding mountains from potential peaks, and update the maximum length as you go. This method ensures O(N) time with constant space and avoids miscounting plateaus or invalid peaks.
Problem Statement
Given an integer array arr, identify the length of the longest contiguous subarray that forms a mountain. A mountain subarray is strictly increasing to a peak, then strictly decreasing, with at least three elements. Return 0 if no valid mountain exists.
For example, arr = [2,1,4,7,3,2,5] contains the longest mountain [1,4,7,3,2] with length 5. Arrays like arr = [2,2,2] contain no mountain and should return 0. Constraints include 1 <= arr.length <= 104 and 0 <= arr[i] <= 104.
Examples
Example 1
Input: arr = [2,1,4,7,3,2,5]
Output: 5
The largest mountain is [1,4,7,3,2] which has length 5.
Example 2
Input: arr = [2,2,2]
Output: 0
There is no mountain.
Constraints
- 1 <= arr.length <= 104
- 0 <= arr[i] <= 104
Solution Approach
Identify Peaks with Two Pointers
Scan the array to find potential peaks where arr[i-1] < arr[i] > arr[i+1]. Use two pointers to expand left and right from each peak to compute the full mountain length. This ensures every valid mountain is counted without revisiting elements unnecessarily.
Dynamic Programming State Tracking
Maintain two state arrays or counters: one for increasing sequences from the left and one for decreasing sequences from the right. At each index, the mountain length can be calculated as left[i] + right[i] + 1. This prevents miscounting plateaus or invalid subsequences.
Update Maximum Length Efficiently
Iterate through all identified peaks and compute their mountain length using the state transitions. Keep a global maximum updated. Skip indexes that cannot form valid mountains to maintain O(N) time complexity with constant extra space.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(1) |
The algorithm runs in O(N) time because each element is visited at most twice: once to compute increasing sequences and once for decreasing sequences. Space is O(1) if counters are used instead of full arrays for left/right states.
What Interviewers Usually Probe
- They may ask about handling plateaus or equal consecutive elements.
- Expect questions on why two pointers suffice instead of nested loops.
- Be ready to explain the state transition from increasing to decreasing sequences.
Common Pitfalls or Variants
Common pitfalls
- Counting plateaus as part of a mountain peak incorrectly.
- Failing to require at least three elements for a valid mountain.
- Overcomplicating the solution with nested loops instead of linear expansion from peaks.
Follow-up variants
- Find the total number of mountains in the array rather than the longest.
- Compute the longest mountain if the array can contain negative numbers.
- Return the indices of the longest mountain subarray instead of its length.
How GhostInterview Helps
- Automatically identifies potential peaks and computes mountain lengths using optimized state transitions.
- Highlights common failure modes like plateaus or invalid sequences for instant debugging.
- Generates step-by-step guidance on two-pointer expansions and dynamic programming application tailored to this problem.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What defines a mountain in the Longest Mountain in Array problem?
A mountain is a contiguous subarray with at least three elements that strictly increases to a peak and then strictly decreases.
Can the array contain plateaus and still form a mountain?
No, equal consecutive elements break the strict increase or decrease requirement, so plateaus are invalid.
Why use two pointers for Longest Mountain in Array?
Two pointers efficiently expand left and right from peaks to calculate mountain lengths in linear time, avoiding nested loops.
What is the time complexity using state transition dynamic programming?
It is O(N) because each element is considered at most twice while computing increasing and decreasing sequences.
How do I handle arrays with no valid mountain?
Return 0 whenever no subarray meets the strict increase-then-decrease criteria with at least three elements.
Need direct help with Longest Mountain in Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Mountain in Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the longest word chain by scanning arrays and using hash lookups to efficiently track predecessor-successor sequences in words.
Open problem page#1537 Get the Maximum ScoreFind the maximum possible score from two sorted arrays with a dynamic programming approach, leveraging partitioning and state transition.
Open problem page#42 Trapping Rain WaterCalculate the total trapped rain water using the elevation map array, leveraging dynamic programming and two-pointer patterns efficiently.
Open problem page