1671. Minimum Number of Removals to Make Mountain Array
Minimum Number of Removals to Make Mountain Array (LeetCode 1671) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
How to solve Minimum Number of Removals to Make Mountain Array
Minimum Number of Removals to Make Mountain Array is a Longest Increasing Subsequence problem, part of Dynamic Programming (DP) Patterns. Find LIS using DP and binary search optimization. O(n log n) solution.
Work towards the solution in these steps:
- Think the opposite direction instead of minimum elements to remove the maximum mountain subsequence
- Think of LIS it's kind of close
The reference solution runs in O(nlogn) time and O(n) space.
The Minimum Number of Removals to Make Mountain Array solution and editorial walks through the full approach with reference code.
Problem statement
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.
Example 1:
Input: nums = [1,3,1] Output: 0 Explanation: 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 Explanation: 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.
Topics and companies
Topics: Array, Binary Search, Dynamic Programming, Greedy.
Reported in interviews at Microsoft.
How to practise Minimum Number of Removals to Make Mountain Array on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.
Open Minimum Number of Removals to Make Mountain Array in the code editor, or read the Minimum Number of Removals to Make Mountain Array editorial for a worked solution with its approach and complexity analysis.
Where Minimum Number of Removals to Make Mountain Array sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- Longest Increasing Subsequence (LIS) subpattern
- The full DSA patterns sheet
Problems related to Minimum Number of Removals to Make Mountain Array
Other problems that use the same Longest Increasing Subsequence (LIS) and Dynamic Programming (DP) Patterns techniques:
- Longest Increasing Subsequence — Medium, same subpattern
- Longest Increasing Subsequence II — Hard, same subpattern
- Russian Doll Envelopes — Hard, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Minimum Number of Removals to Make Mountain Array FAQ
What is the LeetCode number of Minimum Number of Removals to Make Mountain Array?
Minimum Number of Removals to Make Mountain Array is LeetCode problem 1671, rated Hard.
What pattern is used to solve Minimum Number of Removals to Make Mountain Array?
Minimum Number of Removals to Make Mountain Array is a Longest Increasing Subsequence problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
What is the time complexity of Minimum Number of Removals to Make Mountain Array?
The reference solution runs in O(nlogn) time and O(n) space.
Which companies ask Minimum Number of Removals to Make Mountain Array?
Minimum Number of Removals to Make Mountain Array has been reported in interviews at Microsoft.