Longest Mountain in Array — leetcode #845 : A Step-by-Step Guide

The “Longest Mountain in Array” problem is an excellent example of array traversal combined with mathematical reasoning. In this article, we’ll explore the problem, understand its requirements, and solve it step by step in Java.

Problem Statement

You are given an integer array arr. A mountain is defined as a subarray that satisfies the following conditions:

1. The subarray has at least three elements.
2. There exists some iii such that:

• arr[i−1]<arr[i]>arr[i+1]arr[i-1] < arr[i] > arr[i+1]arr[i−1]<arr[i]>arr[i+1] (i.e., arr[i]arr[i]arr[i] is the peak of the mountain).

A mountain must strictly increase to the peak and strictly decrease after the peak. Return the length of the longest mountain in the array. If there is no mountain, return 0.

Example 1:

Input: arr = {2, 1, 4, 7, 3, 2, 5};

Output: 5

Explanation: The mountain is [1,4,7,3,2][1, 4, 7, 3, 2][1,4,7,3,2].

Example 2:

Input: arr = {2, 2, 2};

Output: 0

Explanation: There is no mountain since all elements are equal.

Approach to Solve the Problem

Observations:

1. A valid mountain must have:

• At least one upward slope.
• A peak where the upward slope transitions to a downward slope.
• At least one downward slope.

2. Traverse the array to identify peaks and calculate the lengths of valid mountains.

Algorithm:

1. Use a single traversal approach:

• Start with the second element and end at the second-to-last element since a peak cannot exist at the boundaries.
• Identify peaks and then expand both leftward and rightward to find the boundaries of the mountain.

2. Expand Left and Right:

• From the peak, expand left until the array stops strictly decreasing.
• Similarly, expand right until the array stops strictly decreasing.

3. Track the maximum length of all mountains encountered.

Java Implementation

Here’s the Java implementation for the problem:

public class LongestMountain {
    public static int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) return 0; // A mountain must have at least 3 elements

        int maxLength = 0;

        for (int i = 1; i < n - 1; i++) {
            // Check if arr[i] is a peak
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                int left = i - 1;
                int right = i + 1;

                // Expand left
                while (left > 0 && arr[left] > arr[left - 1]) {
                    left--;
                }

                // Expand right
                while (right < n - 1 && arr[right] > arr[right + 1]) {
                    right++;
                }

                // Calculate the length of the mountain
                int length = right - left + 1;
                maxLength = Math.max(maxLength, length);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 4, 7, 3, 2, 5};
        System.out.println("Longest Mountain Length: " + longestMountain(arr)); // Output: 5
    }
}

Complexity Analysis

Time Complexity:

• The loop iterates over the array once.
• The left and right expansions for each peak are linear, but each element is only traversed once overall.
• Overall Complexity: O(n)O(n)O(n).

Space Complexity:

• The solution uses a constant amount of extra space.
• Space Complexity: O(1)O(1)O(1).

Key Takeaways for Java Developers

1. Use the expansion technique to handle problems with dynamic boundaries.
2. Always think about edge cases, such as:

• Arrays with fewer than 3 elements.
• Arrays where all elements are equal or strictly increasing/decreasing.

3. Carefully choose where to start and end loops to avoid boundary errors.

Example Walkthrough:

Let’s walk through an example:

Input:

arr = {2, 1, 4, 7, 3, 2, 5};

1. Traverse the array:

• At i=3i = 3i=3, arr[3]=7arr[3] = 7arr[3]=7 is a peak (4<7>34 < 7 > 34<7>3).

2. Expand left from 333:

• Stops at 111 (2<12 < 12<1).

3. Expand right from 333:

• Stops at 222 (3>2>53 > 2 > 53>2>5).

4. Mountain length = 555.

Output: 555.

Practice Problems to Reinforce the Concept

1. Find Peak Element
2. Bitonic Array
3. Wiggle Subsequence

With this understanding and implementation, you’re now equipped to solve the “Longest Mountain in Array” problem efficiently in Java. Happy coding!