#1671

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Removals to Make Mountain Array

Solve the problem of finding the minimum number of removals to make a given array a mountain array using dynamic programming and binary search.

array binary search dynamic programming greedy

Problem Statement

You are given an integer array nums. Your task is to return the minimum number of elements to remove to make nums a mountain array.

A mountain array is defined as an array where there exists an element such that all the elements before it form a strictly increasing sequence, and all the elements after it form a strictly decreasing sequence. The solution requires using dynamic programming and binary search to identify the maximum mountain subsequence and calculate the number of removals needed.

Examples

Example 1

Input: nums = [1,3,1]

Output: 0

The array itself is a mountain array so we do not need to remove any elements.

Example 2

Input: nums = [2,1,1,5,6,2,3,1]

Output: 3

One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Constraints

3 <= nums.length <= 1000
1 <= nums[i] <= 109
It is guaranteed that you can make a mountain array out of nums.

Solution Approach

State Transition Dynamic Programming

The key idea is to maximize the length of the longest mountain subsequence by applying dynamic programming in both increasing and decreasing directions. First, calculate the longest increasing subsequence (LIS) up to each element, and then calculate the longest decreasing subsequence (LDS) starting from each element. Combining these subsequences gives us the length of the mountain subsequence.

Binary Search for Efficiency

To efficiently calculate the LIS and LDS, binary search is employed to find the correct position of elements within a sorted list. This improves the time complexity, making the solution feasible even for larger arrays with a time complexity of O(N log N).

Calculating Minimum Removals

Once we have the lengths of the LIS and LDS for each element, the mountain subsequence can be constructed. The number of removals is then simply the total number of elements minus the length of the longest valid mountain subsequence.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

The time complexity of the solution is O(N log N) due to the use of binary search to compute the LIS and LDS. The space complexity is O(N) because we store the LIS and LDS values for each element in the array.

What Interviewers Usually Probe

Look for the candidate's understanding of dynamic programming and binary search techniques.
Evaluate how efficiently the candidate handles the transition between increasing and decreasing subsequences.
Assess the candidate’s ability to optimize the solution using binary search to keep the time complexity manageable.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly distinguish between strictly increasing and strictly decreasing subsequences.
Not optimizing the LIS and LDS computations using binary search, leading to higher time complexity.
Misunderstanding the problem by focusing on removals rather than maximizing the length of the mountain subsequence.

Follow-up variants

Given a non-integer array, apply similar logic to find the maximum subsequence.
Modify the problem to allow for a peak that doesn’t strictly increase or decrease.
Alter the constraints by reducing the array size to test the efficiency of the solution.

FAQ

What is the main approach to solving the 'Minimum Number of Removals to Make Mountain Array' problem?

The main approach involves maximizing the length of the mountain subsequence using dynamic programming and binary search, instead of focusing on removals directly.

What makes this problem 'hard' in LeetCode?

The challenge comes from efficiently applying dynamic programming combined with binary search to find the longest increasing and decreasing subsequences, while keeping the time complexity low.

What are the key pitfalls to avoid in this problem?

Common pitfalls include incorrect handling of the subsequence directions (increasing vs. decreasing) and inefficient computation of LIS/LDS without using binary search.

How does binary search improve the solution?

Binary search helps to efficiently find the correct positions for elements when calculating LIS and LDS, reducing the time complexity to O(N log N).

How can I optimize my solution for large arrays?

To optimize the solution for large arrays, use binary search when calculating LIS and LDS to ensure the time complexity remains manageable at O(N log N).

terminal

Solution

Solution 1: Dynamic Programming

This problem can be transformed into finding the longest increasing subsequence and the longest decreasing subsequence.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    left[i] = max(left[i], left[j] + 1)
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if nums[i] > nums[j]:
                    right[i] = max(right[i], right[j] + 1)
        return n - max(a + b - 1 for a, b in zip(left, right) if a > 1 and b > 1)

Continue Practicing

#2439 minimize maximum of array #2560 house robber iv #2616 minimize the maximum difference of pairs