LeetCode 3231: Minimum Number of Increasing Subsequence to Be Removed Solution

Master LeetCode problem 3231 (Minimum Number of Increasing Subsequence to Be Removed), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3231. Minimum Number of Increasing Subsequence to Be Removed

Hard

Array Binary Search

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through the array and for each element, we will keep track of the maximum increasing subsequence ending at that element. Then, we can iterate backwards through the array to find the maximum increasing subsequence starting from each element. By combining these two values, we can get the length of the longest increasing subsequence that includes each element. The minimum number of elements to remove will be the total number of elements minus the length of the longest increasing subsequence.

Algorithm:

Initialize two arrays incFromLeft and incFromRight of size equal to the input array.
Fill incFromLeft array by finding the maximum increasing subsequence ending at each element from left to right.
Fill incFromRight array by finding the maximum increasing subsequence starting at each element from right to left.
For each element in the array, find the length of the longest increasing subsequence that includes that element.
Return the minimum number of elements to be removed, which is the total number of elements minus the maximum length found in step 4.

Time Complexity: O(n^2) Space Complexity: O(n)

Solution Code

class Solution {
    public int minNumberToRemove(int[] nums) {
        int n = nums.length;
        int[] incFromLeft = new int[n];
        int[] incFromRight = new int[n];
        
        // Find the maximum increasing subsequence ending at each element from left to right
        for (int i = 0; i < n; i++) {
            incFromLeft[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    incFromLeft[i] = Math.max(incFromLeft[i], incFromLeft[j] + 1);
                }
            }
        }
        
        // Find the maximum increasing subsequence starting at each element from right to left
        for (int i = n - 1; i >= 0; i--) {
            incFromRight[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (nums[j] < nums[i]) {
                    incFromRight[i] = Math.max(incFromRight[i], incFromRight[j] + 1);
                }
            }
        }
        
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            maxLength = Math.max(maxLength, incFromLeft[i] + incFromRight[i] - 1);
        }
        
        return n - maxLength;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3231 (Minimum Number of Increasing Subsequence to Be Removed)?

This page provides optimized solutions for LeetCode problem 3231 (Minimum Number of Increasing Subsequence to Be Removed) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3231 (Minimum Number of Increasing Subsequence to Be Removed)?

The time complexity for LeetCode 3231 (Minimum Number of Increasing Subsequence to Be Removed) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3231 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3231 in Java, C++, or Python.

Back to LeetCode Solutions