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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Removals to Make Mountain Array

Number: 1766

Difficulty: Hard

Paid? No

Companies: Meta, PayPal, Amazon, Microsoft

Problem Description

Given an integer array nums, you are tasked with making the array a mountain array by removing the minimum number of elements. An array is called a mountain array if:

  • Its length is at least 3.
  • There exists an index i (0-indexed) where 0 < i < nums.length - 1, such that:
    • nums[0] < nums[1] < ... < nums[i - 1] < nums[i]
    • nums[i] > nums[i + 1] > ... > nums[nums.length - 1] Return the minimum number of removals required to obtain such a mountain array. It is guaranteed that a mountain array can be made from the input.

Key Insights

  • We need to choose a "peak" index such that the subarray before it is strictly increasing and the subarray after it is strictly decreasing.
  • For each index i, compute:
    • lis[i]: Length of the longest increasing subsequence ending at i.
    • lds[i]: Length of the longest decreasing subsequence starting at i.
  • A valid mountain requires lis[i] > 1 and lds[i] > 1.
  • The maximum valid mountain subarray length is given by lis[i] + lds[i] - 1 for a chosen peak.
  • Minimum removals = Total length - (maximum length of valid mountain subarray).

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n), for the two DP arrays (lis and lds)

Solution

We use a dynamic programming approach to compute two arrays:

  1. lis: For every index i, compute the length of the longest strictly increasing subsequence ending at i.
  2. lds: For every index i, compute the length of the longest strictly decreasing subsequence starting at i.

After computing these, iterate over each index and check if both lis[i] and lds[i] are greater than 1, indicating a potential mountain peak. For each valid peak, calculate the mountain length as lis[i] + lds[i] - 1, and keep track of the maximum mountain length found.

Finally, the answer is obtained by subtracting the maximum mountain length from the total number of elements in the array.

Code Solutions

# Python solution for Minimum Number of Removals to Make Mountain Array

def minimumMountainRemovals(nums):
    n = len(nums)
    # Dynamic Programming arrays for increasing and decreasing subsequences
    lis = [1] * n  # lis[i] holds the length of the longest increasing subsequence ending at i
    lds = [1] * n  # lds[i] holds the length of the longest decreasing subsequence starting at i

    # Compute longest increasing subsequence for each index
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                lis[i] = max(lis[i], lis[j] + 1)

    # Compute longest decreasing subsequence for each index going from right to left
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i]:
                lds[i] = max(lds[i], lds[j] + 1)

    maxMountain = 0
    # Check for valid mountain peak indices (peak must have at least one element before and after)
    for i in range(1, n - 1):
        if lis[i] > 1 and lds[i] > 1:
            maxMountain = max(maxMountain, lis[i] + lds[i] - 1)

    # Return the minimum removals required to get a mountain array
    return n - maxMountain

# Example usage:
nums = [2,1,1,5,6,2,3,1]
print(minimumMountainRemovals(nums))  # Expected output: 3
← Back to All Questions