How do you solve Longest Mountain in Array on LeetCode?

Longest Mountain in Array (LeetCode #845) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: A mountain must have a peak with elements strictly increasing before and strictly decreasing after it.

What is the brute force solution for Longest Mountain in Array?

The brute force approach for Longest Mountain in Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every possible subarray to see if it forms a mountain. This is straightforward but inefficient, as it requires examining all combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Longest Mountain in Array?

Longest Mountain in Array uses the following concepts: Array, Two Pointers, Dynamic Programming, Enumeration. The recommended patterns to study are: Two Pointers, Sliding Window, Array.

What are the interview tips for Longest Mountain in Array?

Always clarify the problem constraints and edge cases before diving into coding. Think about how you can reduce the number of passes through the data. Practice explaining your thought process as you code, as communication is key in interviews.

What are common mistakes when solving Longest Mountain in Array?

Not checking for the minimum length of 3 for a valid mountain. Confusing the conditions for a peak, leading to incorrect mountain identification.

#845

Longest Mountain in Array

Medium

ArrayTwo PointersDynamic ProgrammingEnumerationTwo PointersSliding WindowArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses a single pass to identify the mountains by tracking the lengths of increasing and decreasing sequences. This reduces the time complexity significantly.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers to track the length of the increasing and decreasing sequences.
2Step 2: Traverse the array while checking for peaks and counting lengths of increasing and decreasing sequences.
3Step 3: Whenever a peak is found, calculate the total length and update the maximum length.

solution.py19 lines

1# Full working Python code
2
3def longestMountain(arr):
4    n = len(arr)
5    max_length = 0
6    i = 1
7    while i < n - 1:
8        if arr[i - 1] < arr[i] > arr[i + 1]:  # Peak check
9            left = i - 1
10            right = i + 1
11            while left > 0 and arr[left - 1] < arr[left]:
12                left -= 1
13            while right < n - 1 and arr[right] > arr[right + 1]:
14                right += 1
15            max_length = max(max_length, right - left + 1)
16            i = right  # Move to the end of the mountain
17        else:
18            i += 1
19    return max_length

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the array, checking each element once. The space complexity is O(1) since we use a constant amount of extra space.

1A mountain must have a peak with elements strictly increasing before and strictly decreasing after it.
2The longest mountain can be found by efficiently tracking peaks and their boundaries.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.