We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Removals to Make Mountain Array

Difficulty: Hard

Problem Description

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 nums, return the minimum number of elements to remove to make nums a mountain array.

Key Insights

  • The array must have a peak, which is the highest point, and elements must ascend to the peak and descend afterwards.
  • We can utilize dynamic programming to find the longest increasing subsequence (LIS) for the ascending part and the longest decreasing subsequence (LDS) for the descending part.
  • The total removals needed will be the total number of elements minus the longest valid mountain sequence.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can break it into two main parts: finding the longest increasing subsequence (LIS) and the longest decreasing subsequence (LDS) from the input array.

  1. First, we will compute the LIS for every index in the array. This represents the maximum number of elements we can have before the peak.
  2. Then, we will compute the LDS for each index in reverse order. This represents the maximum number of elements we can have after the peak.
  3. The peak index can be any index between the first and the last index, and we will find the maximum value of LIS[i] + LDS[i] - 1 (subtracting 1 because the peak element is counted twice).
  4. Finally, the minimum number of removals will be the total number of elements minus the maximum valid mountain length.

Code Solutions

def minimumRemovals(nums):
    n = len(nums)

    # Step 1: Compute LIS
    lis = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    # Step 2: Compute LDS
    lds = [1] * n
    for i in range(n-2, -1, -1):
        for j in range(n-1, i, -1):
            if nums[i] > nums[j]:
                lds[i] = max(lds[i], lds[j] + 1)

    # Step 3: Find the maximum mountain length
    max_mountain_length = 0
    for i in range(1, n-1):
        if lis[i] > 1 and lds[i] > 1:  # Ensure it can form a mountain
            max_mountain_length = max(max_mountain_length, lis[i] + lds[i] - 1)

    # Step 4: Calculate the minimum removals
    return n - max_mountain_length
← Back to All Questions