Introduction

In this blog post, we will explore how to solve the LeetCode problem "845" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 < i < arr.length - 1 such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > 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?

Explanation

• Identify Potential Peaks: Iterate through the array and check each element to see if it could be a peak of a mountain subarray (i.e., it's greater than its neighbors).
  • Expand from Peak: For each potential peak, expand outwards in both directions (left and right) as long as the mountain condition (increasing to the left, decreasing to the right) holds.
  • Track Maximum Length: Keep track of the maximum length of any mountain found so far and update it whenever a longer mountain is encountered.

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

Code

    def longestMountain(arr: list[int]) -> int:
    """
    Finds the length of the longest mountain subarray in the given array.

    Args:
        arr: The input array of integers.

    Returns:
        The length of the longest mountain subarray.
    """

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

    max_len = 0
    i = 1
    while i < n - 1:
        # Check if arr[i] is 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

            max_len = max(max_len, right - left + 1)
            i = right  # Jump to the end of the mountain to avoid overlapping checks
        else:
            i += 1

    return max_len