algoadvance

Leetcode 845. Longest Mountain in Array

Problem Statement

You are given an integer array arr. A mountain in an array consists of elements that are strictly increasing until they reach a peak (the peak element) and then are strictly decreasing.

The mountain must have at least three elements (one for the increasing part, one as the peak, and one for the decreasing part).

Write a function that returns the length of the longest mountain in the array. If there is no mountain, return 0.

Example:

• 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:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

Clarifying Questions

1. Are negative numbers allowed?
   • No, all elements are non-negative integers.
2. Can the peaks of different mountains be points not surrounded by increasing and decreasing sequences?
   • No, a valid mountain has elements strictly increasing to a single peak and then strictly decreasing.

Strategy

1. Traverse the array while looking out for potential peaks (elements that are greater than their neighbors).
2. For each peak, expand outwards to the left to find the starting point of the increasing sequence.
3. Similarly, expand outwards to the right to enforce the decreasing sequence.
4. Calculate the length of the mountain for every peak and keep track of the maximum length found.
5. Return the maximum length found. If no mountain is identified, return 0.

Time Complexity

• This approach guarantees that each element in the array is visited a constant number of times, making the time complexity O(n), where n is the length of the array.
• Space complexity is O(1) since we are only using a few extra variables.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        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 to the left
                while (left > 0 && arr[left] > arr[left - 1]) {
                    left--;
                }

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

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

                // Move i to the end of the current mountain to avoid redundant checks
                i = right;
            }
        }

        return maxLength;
    }
};

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?