Leetcode Problem 1671. Minimum Number of Removals to Make Mountain Array

1671. Minimum Number of Removals to Make Mountain Array

Leetcode Solutions

Dynamic Programming - Longest Increasing Subsequence (LIS) from both sides

  1. Initialize two arrays leftLIS and rightLIS of the same length as the input array nums to store the length of the LIS ending and starting at each element, respectively.
  2. Fill the leftLIS array by computing the LIS for each element from left to right.
  3. Fill the rightLIS array by computing the LIS for each element from right to left.
  4. Initialize a variable maxLen to keep track of the maximum length of the bitonic subsequence found.
  5. Iterate through the array and for each element, if both leftLIS[i] and rightLIS[i] are greater than or equal to 2, calculate the length of the bitonic subsequence as leftLIS[i] + rightLIS[i] - 1 and update maxLen if it's greater.
  6. The result is the total number of elements in the array minus maxLen, which represents the minimum number of elements to remove.
UML Thumbnail

Greedy Approach with Stack and Binary Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...