845. Longest Mountain in Array

Longest Mountain in Array (LeetCode 845) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Product Except Self (Prefix/Suffix Products) subpattern.

How to solve Longest Mountain in Array

Longest Mountain in Array is a Product of Array Except Self problem, part of Array/Matrix Manipulation Patterns. Master the prefix and suffix products technique to calculate product of array except self without division.

Work towards the solution in these steps:

1. Consider how you can identify increasing and decreasing sequences within the array to find potential mountain subarrays.
2. Think about using prefix and suffix arrays to store the lengths of increasing and decreasing sequences ending or starting at each index.
3. How can you combine the information from prefix and suffix arrays to determine the length of a mountain centered at each position?

The reference solution runs in O(n) time and O(1) space.

The Longest Mountain in Array solution and editorial walks through the full approach with reference code.

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 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?

Topics and companies

Topics: Two Pointers.

Reported in interviews at Amazon, Paypal.

How to practise Longest Mountain in Array on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Longest Mountain in Array in the code editor, or read the Longest Mountain in Array editorial for a worked solution with its approach and complexity analysis.

Where Longest Mountain in Array sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Product Except Self (Prefix/Suffix Products) subpattern
• The full DSA patterns sheet

Problems related to Longest Mountain in Array

Other problems that use the same Product Except Self (Prefix/Suffix Products) and Array/Matrix Manipulation Patterns techniques:

• Product of Array Except Self — Medium, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Concatenation of Array — Easy, same pattern
• Contains Duplicate — Easy, same pattern
• Design HashSet — Easy, same pattern

Longest Mountain in Array FAQ