1. Problem Statement
Given an array arr[] of size n, we need to divide its elements into:
Each array element can be used in at most one of these subsequences. Some elements may be left unused.
Our goal is to minimize the number of unused elements.
Equivalently:
Maximize the number of elements that can be included in the two subsequences.
Finally:
Answer = n - maximum number of selected elements
2. Example
Consider:
arr = [7, 8, 1, 2, 4, 6, 3, 5, 2, 1, 8, 7]
One possible solution is:
Increasing: [1, 2, 4, 5, 8]
Decreasing: [7, 6, 3, 2, 1]
Total selected:
5 + 5 = 10
Array size:
n = 12
Therefore:
Unused = 12 - 10
= 2
So the answer is:
2
3. Why Is This a Dynamic Programming Problem?
When we process the array from left to right, every element has three possibilities.
Option 1 — Put It in Increasing Subsequence
For example:
Increasing = [1, 2, 4]
Current element = 5
Since:
5 > 4
we can add 5.
Option 2 — Put It in Decreasing Subsequence
For example:
Decreasing = [8, 6, 3]
Current element = 2
Since:
2 < 3
we can add 2.
Option 3 — Don't Use It
The current element can simply be ignored.
Therefore, at every element we have up to three choices.
The difficulty is that we need to remember the last element of both subsequences. That's where DP comes in.
4. DP State
We use:
dp[i][j]
where:
The value stored in dp[i][j] is:
The maximum number of elements selected so far.
For example:
dp[4][7]
means:
Increasing subsequence ends at arr[4]
Decreasing subsequence ends at arr[7]
and the value tells us how many elements have been selected.
5. What About an Empty Subsequence?
Initially, both subsequences are empty.
There is no index representing an empty subsequence. So we use:
n
as a special/virtual index.
Therefore:
dp[n][n] = 0;
means:
Increasing subsequence = empty
Decreasing subsequence = empty
Selected elements = 0
This is a very useful DP technique: using an extra index as a sentinel.
6. Processing Each Element
Suppose the current element is:
arr[k]
We examine every possible DP state:
dp[i][j]
There are three transitions.
7. Transition 1 — Skip the Element
The easiest case is to leave arr[k] unused.
The state doesn't change:
next[i][j] = Math.max(next[i][j], selected);
For example:
Before:
Increasing ends at 4
Decreasing ends at 7
Current element = 10
We may decide not to use 10.
So the state remains unchanged.
8. Transition 2 — Add to Increasing Subsequence
The increasing subsequence must be strictly increasing.
Therefore:
arr[k] > arr[i]
must be true.
There is one special case:
i == n
which means the increasing subsequence is currently empty.
So the condition is:
if (i == n || arr[k] > arr[i])
If valid, we update:
next[k][j] = Math.max(
next[k][j],
selected + 1
);
Why next[k][j]?
Because after adding arr[k], the last element of the increasing subsequence becomes k.
9. Transition 3 — Add to Decreasing Subsequence
Similarly, the decreasing subsequence must be strictly decreasing.
Therefore:
arr[k] < arr[j]
must be true.
Again, if:
j == n
the decreasing subsequence is empty.
So:
if (j == n || arr[k] < arr[j])
If valid:
next[i][k] = Math.max(
next[i][k],
selected + 1
);
The increasing subsequence's last index remains i.
The decreasing subsequence's last index becomes k.
10. Why Do We Need next[][]?
This is an important part of the implementation.
Suppose we are processing:
arr[k]
We should not immediately modify dp.
Instead, we calculate all possibilities in:
next
Then after processing the current element:
dp = next;
This means:
dp → states before processing arr[k]
next → states after processing arr[k]
This prevents the same element from accidentally being used multiple times during the same iteration.
11. Complete Java Code
class Solution {
public int minCount(int[] arr) {
int n = arr.length;
// dp[i][j]:
// i = last index of increasing subsequence
// j = last index of decreasing subsequence
//
// n is used as a virtual index meaning "empty".
int[][] dp = new int[n + 1][n + 1];
// -1 means this state is not reachable.
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = -1;
}
}
// Initially both subsequences are empty.
dp[n][n] = 0;
// Process every array element.
for (int k = 0; k < n; k++) {
int[][] next = new int[n + 1][n + 1];
// Initialize next states.
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
next[i][j] = -1;
}
}
// Try every existing state.
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// State is not reachable.
if (dp[i][j] == -1) {
continue;
}
int selected = dp[i][j];
// ------------------------------------------------
// Option 1: Don't use arr[k]
// ------------------------------------------------
next[i][j] = Math.max(
next[i][j],
selected
);
// ------------------------------------------------
// Option 2: Add arr[k] to increasing subsequence
// ------------------------------------------------
if (i == n || arr[k] > arr[i]) {
next[k][j] = Math.max(
next[k][j],
selected + 1
);
}
// ------------------------------------------------
// Option 3: Add arr[k] to decreasing subsequence
// ------------------------------------------------
if (j == n || arr[k] < arr[j]) {
next[i][k] = Math.max(
next[i][k],
selected + 1
);
}
}
}
// Move to the next element.
dp = next;
}
// Find the maximum number of selected elements.
int maxSelected = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
maxSelected = Math.max(
maxSelected,
dp[i][j]
);
}
}
// Minimum elements that cannot be selected.
return n - maxSelected;
}
}
12. Dry Run with a Small Example
Consider:
arr = [1, 4, 2, 3]
We can choose:
Increasing = [1, 2, 3]
Decreasing = [4]
All 4 elements are used.
Therefore:
answer = 4 - 4 = 0
Initially
dp[n][n] = 0
Both subsequences are empty.
Process 1
1 can be placed into the increasing subsequence:
Increasing = [1]
or the decreasing subsequence:
Decreasing = [1]
or skipped.
Process 4
If increasing ends with 1:
1 < 4
so:
Increasing = [1, 4]
is possible.
Alternatively, 4 can start the decreasing subsequence.
Process 2
If increasing currently ends at 1:
1 < 2
so:
Increasing = [1, 2]
is possible.
If decreasing ends at 4:
2 < 4
so:
Decreasing = [4, 2]
is also possible.
Process 3
We can eventually obtain:
Increasing = [1, 2, 3]
Decreasing = [4]
All elements are selected.
Thus:
maxSelected = 4
answer = 4 - 4 = 0
13. Why Strict Comparison Is Important
The problem specifically says strictly increasing and strictly decreasing.
Therefore:
Increasing
arr[k] > arr[i]
not:
arr[k] >= arr[i]
Decreasing
arr[k] < arr[j]
not:
arr[k] <= arr[j]
For example:
[1, 2, 2, 3]
We cannot have:
[1, 2, 2, 3]
as an increasing subsequence because the two 2s are equal.
14. Why Every Element Is Used at Most Once
At each iteration, the current element arr[k] is placed into one of:
Increasing
or:
Decreasing
or:
Unused
When we put it into the increasing subsequence:
next[k][j]
When we put it into the decreasing subsequence:
next[i][k]
We never transition from the same state by adding arr[k] to both subsequences simultaneously.
Therefore, an element cannot be counted twice.
15. Why Do We Maximize Selected Elements?
The question asks:
What is the minimum number of elements that cannot be included?
Instead of directly minimizing unused elements, we maximize used elements.
If:
n = total elements
and:
maxSelected = maximum elements included
then:
minimum unused = n - maxSelected
This transformation makes the DP much easier.
16. Complexity Analysis
There are:
(n + 1) × (n + 1)
DP states.
For every array element, we visit all states.
Therefore:
Time Complexity = O(n³)
because:
n elements
× n possible i values
× n possible j values
= O(n³)
The DP table contains:
(n + 1) × (n + 1)
elements.
So:
Space Complexity = O(n²)
Although the problem's expected auxiliary space is listed as O(n³), this implementation actually uses only O(n²) auxiliary space because we maintain only the current and next DP tables.
17. Key Takeaway
The most important idea to remember is:
Track the last element of both subsequences.
For every new element:
Current element
|
+------------+------------+
| | |
Increase Decrease Skip
| | |
arr[k] > arr[i] arr[k] < arr[j]
The DP state:
dp[i][j]
captures everything we need to know about the two subsequences.
Finally:
return n - maxSelected;
gives the minimum number of elements that cannot belong to either subsequence.
Join the conversation! Your thoughts help the community grow.