We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Mountain in Array

Difficulty: Medium

Problem Description

Given an integer array arr, return the length of the longest subarray that is a mountain. A mountain array is defined as having a peak with elements strictly increasing to the peak and strictly decreasing after the peak. Return 0 if there is no mountain subarray.

Key Insights

  • A valid mountain must have at least one peak surrounded by elements that strictly increase to the peak and strictly decrease after.
  • The length of a mountain array is determined by the peak and the longest increasing and decreasing subarrays around it.
  • The solution should efficiently traverse the array to find peaks and calculate lengths.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer approach to traverse the array and identify mountains. We will keep track of the length of the mountain by:

  1. Iterating through the array to find peaks (where arr[i-1] < arr[i] > arr[i+1]).
  2. Expanding left and right from the peak to count the length of the mountain.
  3. Keeping track of the maximum length encountered.

This approach ensures that we only pass through the array once, maintaining O(n) time complexity and O(1) space complexity.

Code Solutions

def longestMountain(arr):
    n = len(arr)
    if n < 3:
        return 0

    max_length = 0
    i = 1
    while i < n - 1:
        # Check if we found a peak
        if arr[i - 1] < arr[i] > arr[i + 1]:
            left = i - 1
            right = i + 1
            
            # Expand left
            while left > 0 and arr[left - 1] < arr[left]:
                left -= 1
            # Expand right
            while right < n - 1 and arr[right] > arr[right + 1]:
                right += 1
            
            # Calculate the length of the mountain
            max_length = max(max_length, right - left + 1)
            i = right  # move i to the end of the mountain
        else:
            i += 1
    
    return max_length
← Back to All Questions