algoadvance

You are given an integer array arr. A mountain is defined as a sequence of three or more consecutive elements:

Here, peak is the peak index of the mountain. Given this, you need to find the length of the longest mountain. Return 0 if there is no mountain.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The longest 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:

Clarifying Questions

  1. Are we allowed to modify the input array?
    • No, we assume the input array should remain unchanged.
  2. What should be returned if there are multiple mountains with the same maximum length?
    • Return the length of any one of the longest mountains.
  3. Is there any specific edge cases we need to handle?
    • Yes, handle edge cases where the array length is less than 3 and no valid mountain formation is possible.

Strategy

To solve this problem, we will:

  1. Traverse the array to identify possible peaks (elements that are greater than their neighbors).
  2. For each peak, extend leftward and rightward to determine the boundary of the mountain.
  3. Calculate the length of each identified mountain and keep track of the maximum length found.

Code

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

    for i in range(1, n - 1):
        if arr[i - 1] < arr[i] > arr[i + 1]:  # Identify peak
            left = i - 1
            right = i + 1
            
            # Extend leftward
            while left > 0 and arr[left] > arr[left - 1]:
                left -= 1
                
            # Extend rightward
            while right < n - 1 and arr[right] > arr[right + 1]:
                right += 1
                
            # Calculate current mountain length
            current_length = right - left + 1
            max_length = max(max_length, current_length)

    return max_length

# Test case
arr1 = [2,1,4,7,3,2,5]
print(longestMountain(arr1))  # Output: 5

arr2 = [2,2,2]
print(longestMountain(arr2))  # Output: 0

Time Complexity

The algorithm runs in O(n) time complexity, where n is the length of the array. Each element is visited a constant number of times, making it efficient for large arrays.

Summary

This solution efficiently finds the longest mountain by identifying peaks and extending boundaries to measure the entire length of each mountain while scanning the array only once. This makes it suitable for the input constraints.

Try our interview co-pilot at AlgoAdvance.com