Leetcode 845. Longest Mountain in Array

Let's understand what we're being asked to do. We have an array like [1, 3, 5, 4, 3, 2, 1, 6, 7] and need to find the longest mountain subarray.

A mountain is a sequence that strictly increases then strictly decreases. For example, [1, 3, 5, 4, 3, 2, 1] is a mountain (increases to 5, then decreases). The minimum length is 3 (at least one up, one peak, one down).

Tracing through [1, 3, 5, 4, 3, 2, 1, 6, 7]: we see [1, 3, 5, 4, 3, 2, 1] forms a mountain of length 7. The sequence [1, 6, 7] at the end is only increasing (no descent), so it's not a mountain.

Important constraints: The sequence must be strictly increasing then strictly decreasing (no plateaus like [1, 2, 2, 1]). The peak cannot be at the start or end of the array.

Edge cases to consider: What if no mountain exists? (return 0). What if the array has fewer than 3 elements? What if there are multiple mountains? (return the longest one). What about [1, 2, 3] (only increasing) or [3, 2, 1] (only decreasing)?

The brute force approach checks every possible subarray to see if it forms a valid mountain. For each starting position, try all possible ending positions, and for each subarray, verify if it's strictly increasing up to some peak, then strictly decreasing after. This requires checking all O(n²) subarrays and validating each one, which takes O(n) time per subarray. While straightforward, this approach is inefficient because it rechecks the same elements multiple times and doesn't leverage the structure of mountains.

def longest_mountain(arr):
    """
    Find the longest contiguous mountain subarray.
    A mountain is strictly increasing then strictly decreasing, length >= 3.
    Brute force: check all possible subarrays.
    """
    n = len(arr)
    if n < 3:
        return 0
    
    max_length = 0
    
    # Try every possible starting position
    for start in range(n):
        # Try every possible ending position
        for end in range(start + 2, n):
            # Check if arr[start:end+1] forms a valid mountain
            subarray_length = end - start + 1
            
            # Find the peak (must exist and not be at boundaries)
            peak_found = False
            peak_index = -1
            
            for peak in range(start + 1, end):
                # Check if this is a valid peak
                # Must be strictly increasing before peak
                is_increasing = True
                for i in range(start, peak):
                    if arr[i] >= arr[i + 1]:
                        is_increasing = False
                        break
                
                # Must be strictly decreasing after peak
                is_decreasing = True
                for i in range(peak, end):
                    if arr[i] <= arr[i + 1]:
                        is_decreasing = False
                        break
                
                # If both conditions met, we found a valid mountain
                if is_increasing and is_decreasing:
                    peak_found = True
                    peak_index = peak
                    break
            
            # Update max length if valid mountain found
            if peak_found:
                max_length = max(max_length, subarray_length)
    
    return max_length

A mountain has a peak - the highest point where the sequence transitions from increasing to decreasing. Every valid mountain must have exactly one peak.

Once we identify a peak (where arr[i-1] < arr[i] > arr[i+1]), we can expand outward in both directions to measure the full mountain's length.

By focusing on peaks, we transform the problem from 'find all possible subarrays' into 'find peaks and measure their mountains'.

This means we can solve it in one pass through the array, checking each potential peak and expanding to measure its mountain, rather than checking every possible subarray combination.

Think about hiking a mountain range. You can identify mountains by finding the peaks (summits).

Once you spot a peak, you can trace down both sides to see where the mountain starts and ends. The mountain's 'length' is the distance from base to base, passing through the peak. Some peaks might have longer descents than others, making their mountains longer overall.

The optimal approach identifies peaks and expands outward to measure mountains in a single pass. For each index, check if it's a peak (both neighbors are smaller). If it is, use two pointers to expand left (while strictly decreasing) and right (while strictly decreasing) to find the mountain's base on both sides. Calculate the mountain length and track the maximum. This approach efficiently measures each mountain exactly once without redundant checks, achieving linear time complexity.

def longest_mountain(arr):
    """
    Find the longest contiguous mountain subarray.
    A mountain is a strictly increasing sequence followed by a strictly decreasing sequence.
    Minimum length is 3.
    """
    if len(arr) < 3:
        return 0
    
    max_length = 0
    i = 1
    
    # Iterate through potential peaks
    while i < len(arr) - 1:
        # Check if current index is a peak
        if arr[i - 1] < arr[i] > arr[i + 1]:
            # Expand left to find base
            left = i - 1
            while left > 0 and arr[left - 1] < arr[left]:
                left -= 1
            
            # Expand right to find base
            right = i + 1
            while right < len(arr) - 1 and arr[right] > arr[right + 1]:
                right += 1
            
            # Calculate mountain length
            current_length = right - left + 1
            max_length = max(max_length, current_length)
            
            # Move to end of current mountain
            i = right
        else:
            i += 1
    
    return max_length

• Peak-based window expansion: When detecting mountain-like patterns, identify peaks first (elements greater than both neighbors), then expand bidirectionally to measure the full structure - this avoids redundant scanning and naturally handles the "strictly increasing then decreasing" constraint.
• Single-pass state machine: Track up-count and down-count as you traverse, resetting when the pattern breaks (flat or direction reversal during ascent) - this O(n) time, O(1) space approach eliminates the need for multiple passes or auxiliary data structures.
• Strict inequality enforcement: Use `arr[i] > arr[i+1]` (not `>=`) for both ascending and descending phases - mountains require strictly monotonic sequences, and allowing equality creates invalid plateaus that don't qualify as mountains.
• Boundary validation pitfall: Always verify both up > 0 AND down > 0 before calculating mountain length - a common mistake is counting sequences that only go up or only go down, which violates the "peak must exist" requirement (minimum length 3 means at least 1 up, 1 peak, 1 down).
• Reset logic precision: Reset counters to current position's state (not zero) when transitioning from down-to-up - if `arr[i] < arr[i+1]` after descending, set `up=1, down=0` to start a new potential mountain, avoiding off-by-one errors in overlapping mountain detection.
• Contiguous subarray pattern: This sliding window variant applies to any problem requiring maximal contiguous sequences with state transitions (stock prices with peaks/valleys, temperature fluctuations, signal processing) - the key is identifying when to expand, measure, and reset your window based on pattern validity.