Minimum Elements Outside Subsequences

Problem Overview

Each array value may join a strictly increasing chain, a strictly decreasing chain, or stay unused.

Intuition

Each array value may join a strictly increasing chain, a strictly decreasing chain, or stay unused. An element cannot sit in both chains. Track the last index placed on each chain and decide per position whether to skip or extend one chain while preserving strict order.

Algorithm

1DP state: minimum skipped count from idx with given incLast and decLast.
2Base at idx = n is 0 skipped.
3From idx backward: skip costs 1 + next[inc][dec].
4If arr[idx] beats the inc tail, try placing on inc with new tail idx.
5If arr[idx] is below the dec tail, try placing on dec similarly.
6Use two (n+1) by (n+1) layers and roll after each idx.

Example Walkthrough

Input: arr = [1, 4, 2, 3, 3, 2, 4]

1. One inc chain can be 1, 2, 3, 4 in order.
2. One dec chain can be 4, 3, 2 using later values.
3. Every element fits, so zero are left outside.

Output: 0

Common Pitfalls

• Strict inequalities: equal values cannot extend the same chain.
• Store last indices, not values, so transitions compare arr[idx] to arr[last].
• Shift -1 tails to index 0 in the table with last + 1.
• Time is O(n^3); rolling layers cut space from O(n^3) to O(n^2).

Minimum Elements Outside Subsequences.java

Java

// Approach: At each index, skip the element or place it on a strict inc/dec chain.
// State is the last index used in each chain. Bottom-up with two 2D layers because
// only the next index row is needed. Minimize skipped elements directly.
// Complexity: O(n^3) time and O(n^2) extra space.

class Solution {

    public int minCount(int[] arr) {
        int n = arr.length;
        int[][] next = new int[n + 1][n + 1];
        int[][] curr = new int[n + 1][n + 1];

        for (int idx = n - 1; idx >= 0; idx--) {
            for (int incLast = -1; incLast < n; incLast++) {
                for (int decLast = -1; decLast < n; decLast++) {
                    int ans = 1 + next[incLast + 1][decLast + 1];

                    if (incLast == -1 || arr[idx] > arr[incLast]) {
                        ans = Math.min(ans, next[idx + 1][decLast + 1]);
                    }
                    if (decLast == -1 || arr[idx] < arr[decLast]) {
                        ans = Math.min(ans, next[incLast + 1][idx + 1]);
                    }

                    curr[incLast + 1][decLast + 1] = ans;
                }
            }

            int[][] temp = next;
            next = curr;
            curr = temp;
        }

        return next[0][0];
    }
}

Was this solution helpful?