Problem Statement
You are given an integer array arr[]. Your task is to find the minimum number of elements to delete so that the remaining elements form a strictly increasing sequence while maintaining their original order.
Example 1
Input
arr = [5, 6, 1, 7, 4]
Output
2
Explanation
Remove 1 and 4.
Remaining array:
[5, 6, 7]
This is strictly increasing.
Example 2
Input
arr = [1, 1, 1]
Output
2
Explanation
A strictly increasing sequence cannot contain duplicate values.
Remove any two elements.
Remaining:
[1]
Observation
Instead of thinking about which elements to delete, think about:
Which elements should we keep?
The longest sequence that is already strictly increasing is called the Longest Increasing Subsequence (LIS).
If the LIS length is L, then:
Minimum Deletions = Total Elements - LIS Length
Why?
Suppose:
Array = [5, 6, 1, 7, 4]
Longest Increasing Subsequence:
[5, 6, 7]
Length:
3
Total elements:
5
Minimum deletions:
5 - 3 = 2
Exactly what we need.
Efficient Approach (O(n log n))
A normal Dynamic Programming solution takes O(n²).
Since n can be 100000, O(n²) will cause a Time Limit Exceeded error.
Instead, we use the Binary Search LIS Algorithm.
Idea
Maintain an ArrayList called:
lis
This does not always store the actual LIS.
Instead:
lis[i]
stores the smallest possible ending value of an increasing subsequence of length (i + 1).
Smaller ending values help us build longer increasing subsequences later.
Dry Run
Array:
[5, 6, 1, 7, 4]
Initially:
lis = []
Step 1
Current number:
5
No elements exist.
Add it.
lis = [5]
Step 2
Current number:
6
Greater than the last element.
Append.
lis = [5, 6]
Step 3
Current number:
1
Find the first element ≥ 1.
That is:
5
Replace it.
lis = [1, 6]
Notice:
We are not saying the LIS became [1, 6].
Instead, we found a better ending value.
Step 4
Current number:
7
Greater than all elements.
Append.
lis = [1, 6, 7]
Step 5
Current number:
4
First element ≥ 4 is:
6
Replace it.
lis = [1, 4, 7]
Finished.
Length:
3
Minimum deletions:
5 - 3 = 2
Understanding the Code
class Solution
class Solution {
Solution class required by GeeksForGeeks.
public int minDeletions(int[] arr)
public int minDeletions(int[] arr) {
Function returns the minimum number of deletions.
Store Array Size
int n = arr.length;
Store the array size.
Create the lis ArrayList
ArrayList<Integer> lis = new ArrayList<>();
Stores the smallest possible tail values.
Initially empty.
Loop Through Every Element
for (int num : arr)
Take one element at a time.
Binary Search
int idx = Collections.binarySearch(lis, num);
Search the current number inside lis.
Two cases are possible.
Case 1: Element Exists
Example:
lis = [1, 4, 7]
Search:
4
Returns:
1
Case 2: Element Doesn't Exist
Example:
lis = [1, 4, 7]
Search:
5
Java returns:
-3
Why?
Insertion position:
2
Java returns:
-(position + 1)
So:
-(2 + 1)
= -3
Therefore:
if (idx < 0) {
idx = -(idx + 1);
}
Converts:
-3
back into:
2
which is the correct insertion position.
If the Element Is Larger Than All
if (idx == lis.size())
Example:
lis = [1, 4, 7]
num = 9
Insertion position:
3
which equals:
lis.size()
Append:
lis.add(num);
Now:
[1, 4, 7, 9]
Otherwise Replace
else {
lis.set(idx, num);
}
Example:
lis = [1, 6, 7]
num = 4
Replace:
6
Result:
[1, 4, 7]
A smaller tail increases the chance of extending the sequence later.
Return the Answer
return n - lis.size();
Example:
n = 5
LIS = 3
Answer:
5 - 3
= 2
Complete Code
import java.util.*;
class Solution {
public int minDeletions(int[] arr) {
int n = arr.length;
ArrayList<Integer> lis = new ArrayList<>();
for (int num : arr) {
int idx = Collections.binarySearch(lis, num);
if (idx < 0) {
idx = -(idx + 1);
}
if (idx == lis.size()) {
lis.add(num);
} else {
lis.set(idx, num);
}
}
return n - lis.size();
}
}
Complexity Analysis
Time Complexity
Overall:
O(n log n)
Space Complexity
The lis list stores at most n elements.
O(n)
Key Takeaways
We don't directly find which elements to delete.
We first compute the Longest Increasing Subsequence (LIS).
The minimum deletions required are:
Minimum Deletions = n - LIS Length
Summary
To minimize deletions while preserving the original order, compute the Longest Increasing Subsequence (LIS) of the array. The answer is simply the total number of elements minus the LIS length. Using the binary search-based LIS algorithm reduces the time complexity from O(n²) to O(n log n), making it suitable for large input sizes.
Join the conversation! Your thoughts help the community grow.