How do you solve Minimum Number of Removals to Make Mountain Array on LeetCode?

Minimum Number of Removals to Make Mountain Array (LeetCode #1671) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Finding the longest mountain subsequence is crucial to minimizing removals.

What is the brute force solution for Minimum Number of Removals to Make Mountain Array?

The brute force approach for Minimum Number of Removals to Make Mountain Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible subsequences of the array to find the longest mountain subsequence. By determining the longest valid mountain subsequence, we can then calculate how many elements need to be removed. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Minimum Number of Removals to Make Mountain Array?

Minimum Number of Removals to Make Mountain Array uses the following concepts: Array, Binary Search, Dynamic Programming, Greedy. The recommended patterns to study are: Dynamic Programming, Longest Increasing Subsequence.

What are the interview tips for Minimum Number of Removals to Make Mountain Array?

Always discuss your thought process and potential approaches before jumping into coding. Consider both the problem constraints and edge cases when designing your solution. Practice explaining your code and logic clearly, as communication is key in interviews.

What are common mistakes when solving Minimum Number of Removals to Make Mountain Array?

Students often try to brute-force the problem without considering more efficient algorithms. Failing to account for edge cases where the array is already a mountain.

#1671

Minimum Number of Removals to Make Mountain Array

Hard

ArrayBinary SearchDynamic ProgrammingGreedyDynamic ProgrammingLongest Increasing Subsequence

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

Instead of removing elements, we can find the longest mountain subsequence using dynamic programming. We will first find the longest increasing subsequence (LIS) from the left and then from the right, and combine the results to find the longest mountain.

⚙️

Algorithm

5 steps

1Step 1: Create two arrays, left and right, to store the length of the longest increasing subsequence up to each index from the left and right respectively.
2Step 2: Fill the left array using a modified LIS approach.
3Step 3: Fill the right array using a similar approach but from the right side.
4Step 4: For each index, calculate the length of the mountain using left[i] + right[i] - 1 (to avoid double counting the peak).
5Step 5: Find the maximum length of the mountain and subtract it from the total length to get the minimum removals.

solution.py29 lines

1# Full working Python code
2
3def min_removals_to_make_mountain(nums):
4    n = len(nums)
5    if n < 3:
6        return 0
7
8    left = [1] * n
9    right = [1] * n
10
11    # Fill left array
12    for i in range(1, n):
13        for j in range(i):
14            if nums[i] > nums[j]:
15                left[i] = max(left[i], left[j] + 1)
16
17    # Fill right array
18    for i in range(n - 2, -1, -1):
19        for j in range(n - 1, i, -1):
20            if nums[i] > nums[j]:
21                right[i] = max(right[i], right[j] + 1)
22
23    max_length = 0
24    for i in range(1, n - 1):
25        if left[i] > 1 and right[i] > 1:
26            max_length = max(max_length, left[i] + right[i] - 1)
27
28    return n - max_length
29

ℹ

Complexity note: The time complexity is O(n²) due to the nested loops used to fill the left and right arrays, while the space complexity is O(n) for storing the lengths of the subsequences.

1Finding the longest mountain subsequence is crucial to minimizing removals.
2Dynamic programming can efficiently solve the problem by breaking it down into smaller subproblems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.