LeetCode Solutions Blog

Longest Mountain in Array

Number: 875

Difficulty: Medium

Paid? No

Problem Description

Given an array, find the length of the longest subarray that is a mountain. A mountain is defined as a subarray with at least three elements where there exists an index i (0-indexed) such that:

arr[0] < arr[1] < ... < arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1] Return the length of the longest such subarray; if none exists, return 0.

Key Insights

A mountain requires a strictly increasing sequence followed by a strictly decreasing sequence.
The peak element cannot be the first or last element.
Identify the peak and expand left and right to determine the bounds of the mountain.
Use a one-pass scan to detect peaks and measure the length of the mountain from each found peak.
Maintain O(1) extra space by using index variables only.

Space and Time Complexity

Time Complexity: O(n) - We go through the array while scanning for peaks. Space Complexity: O(1) - Only constant extra space is used.

Solution

We solve the problem using a single pass through the array. For every element, we check if it can be considered a mountain peak (i.e. it is greater than its previous and next element). Once a peak is found, we expand to the left to count how many elements are in the strictly increasing sequence and to the right for the strictly decreasing sequence. The mountain length is the sum of these counts plus one (for the peak itself). Keep track of the maximum mountain length encountered. The main challenge is correctly handling edge cases where the mountain might extend beyond adjacent equal values or the array boundaries.

Code Solutions

# Python solution with detailed comments

def longestMountain(arr):
    # Initialize the variable to store the maximum mountain length
    max_mountain_length = 0
    n = len(arr)
    i = 1
    
    # Loop through the array starting from the second element to the second last element
    while i < n - 1:
        # Check if current element is a peak (strictly greater than its neighbors)
        if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
            # Found a peak, now expand left and right to measure the mountain
            left = i - 1
            right = i + 1
            
            # Expand to the left while the sequence is strictly increasing
            while left > 0 and arr[left] > arr[left - 1]:
                left -= 1
            
            # Expand to the right while the sequence is strictly decreasing
            while right < n - 1 and arr[right] > arr[right + 1]:
                right += 1
            
            # Calculate the length of the current mountain and update the maximum if needed
            current_mountain_length = right - left + 1
            max_mountain_length = max(max_mountain_length, current_mountain_length)
            
            # Move i to the end of the current mountain to avoid rechecking elements within it
            i = right
        else:
            # Otherwise move to the next element if no peak is found at the current position
            i += 1
    
    return max_mountain_length

# Example usage:
print(longestMountain([2,1,4,7,3,2,5]))  # Expected output: 5