Problem Statement
You are given two arrays:
a[] of size n
b[] of size m
Your task is to find the minimum number of insertions and deletions required to transform a[] into b[].
Conditions
Example
Input
a = [1, 2, 5, 3, 1]
b = [1, 3, 5]
Output
4
One possible transformation:
[1,2,5,3,1]
↓ Delete 2
[1,5,3,1]
↓ Insert 3
[1,3,5,3,1]
↓ Delete last 3
[1,3,5,1]
↓ Delete last 1
[1,3,5]
Total operations = 4
Observation
There are only two operations:
Suppose some elements are already in the correct relative order.
Should we delete them?
No.
We should keep as many common elements as possible.
That immediately reminds us of the Longest Common Subsequence (LCS).
Why LCS?
Suppose
a = [1,2,5,3,1]
b = [1,3,5]
The longest common subsequence is:
[1,5]
Length = 2
These two elements don't need any operation.
Everything else is either:
Deleted from a
Inserted into b
Hence,
Delete = n − LCS
Insert = m − LCS
Answer = (n − LCS) + (m − LCS)
Problem with Normal LCS
Traditional LCS uses Dynamic Programming.
Complexity:
O(n × m)
Here,
n, m ≤ 100000
That becomes:
100000 × 100000
= 10^10 operations
Impossible.
So we need another idea.
Important Property
The problem gives a special condition:
Array b is sorted and contains distinct elements.
This changes everything.
Instead of finding the LCS directly, we can convert it into an LIS problem.
Step 1: Store the Position of Every Element of b
Example:
b = [1,3,5]
Store:
1 → 0
3 → 1
5 → 2
Using HashMap:
HashMap
1 -> 0
3 -> 1
5 -> 2
Lookup becomes:
O(1)
Step 2: Convert a into Indices
Original:
a = [1,2,5,3,1]
Ignore elements not present in b.
1 → 0
2 → ignore
5 → 2
3 → 1
1 → 0
New array:
[0,2,1,0]
Notice something.
These numbers represent positions inside b.
Step 3: Find LIS
Now compute the Longest Increasing Subsequence.
For:
[0,2,1,0]
LIS is:
[0,1]
Length = 2
or
[0,2]
Length = 2
So,
LCS = LIS = 2
Why Does LIS Work?
Suppose:
b = [10,20,30,40]
Indices:
10 → 0
20 → 1
30 → 2
40 → 3
Now consider:
a = [20,10,30]
After conversion:
[1,0,2]
LIS:
[1,2]
Length = 2
Corresponding elements:
20,30
These are already in the same order as in b.
Increasing indices mean:
That's exactly what LCS requires.
Hence,
LCS of original arrays
=
LIS of mapped indices
Finding LIS Efficiently
Instead of Dynamic Programming (O(n²)), use the Patience Sorting technique.
Maintain an array called lis.
Initially:
[]
Process numbers one by one.
Example:
0
[0]
Next:
2
[0,2]
Next:
1
Binary Search gives position 1.
Replace:
[0,1]
Next:
0
Replace the first element:
[0,1]
Length remains:
2
That is the LIS length.
Binary Search makes every insertion:
O(log n)
Total:
O(n log n)
Dry Run
Input
a = [1,2,5,3,1]
b = [1,3,5]
HashMap
1 → 0
3 → 1
5 → 2
Converted Array
[0,2,1,0]
LIS
Start:
[]
Process 0:
[0]
Process 2:
[0,2]
Process 1:
[0,1]
Process 0:
[0,1]
Length:
2
Therefore,
Delete:
5 − 2 = 3
Insert:
3 − 2 = 1
Answer:
3 + 1 = 4
Correct.
Algorithm
Store every element of b in a HashMap with its index.
Traverse a.
Keep only the elements present in b.
Replace them with their corresponding indices in b.
Find the LIS using Binary Search.
Let the LIS length be L.
Return:
(n − L) + (m − L)
Correctness Proof
Let L be the length of the Longest Increasing Subsequence of the mapped index array.
Every increasing subsequence corresponds to elements appearing in the same relative order in b.
Since b has distinct elements, this increasing subsequence is exactly a common subsequence of a and b.
Therefore, L equals the length of the Longest Common Subsequence (LCS).
The L common elements are kept unchanged.
The remaining n − L elements in a must be deleted.
The remaining m − L elements in b must be inserted.
Hence, the minimum operations are:
(n - L) + (m - L)
Thus, the algorithm is correct.
Complexity Analysis
Building HashMap
O(m)
Traversing a
O(n)
LIS
Each element performs one Binary Search.
O(n log n)
Overall Time Complexity
O(n log n)
Space Complexity
O(n)
Java Implementation
import java.util.*;
class Solution {
public int minInsAndDel(int[] a, int[] b) {
HashMap<Integer, Integer> map = new HashMap<>();
// Store the index of each element in b
for (int i = 0; i < b.length; i++) {
map.put(b[i], i);
}
ArrayList<Integer> indices = new ArrayList<>();
// Convert common elements of a into their indices in b
for (int num : a) {
if (map.containsKey(num)) {
indices.add(map.get(num));
}
}
// Find LIS length
ArrayList<Integer> lis = new ArrayList<>();
for (int x : indices) {
int pos = Collections.binarySearch(lis, x);
if (pos < 0)
pos = -(pos + 1);
if (pos == lis.size())
lis.add(x);
else
lis.set(pos, x);
}
int lcs = lis.size();
return (a.length - lcs) + (b.length - lcs);
}
}
Key Takeaways
The minimum operations depend on the Longest Common Subsequence (LCS).
A direct LCS solution (O(n × m)) is too slow for large inputs.
Since b is sorted with distinct elements, we can map its values to indices.
The LCS problem transforms into finding the Longest Increasing Subsequence (LIS) of those indices.
Using the Patience Sorting technique with Binary Search computes the LIS in O(n log n), satisfying the problem's constraints.
Summary
The minimum number of insertions and deletions required to transform one array into another can be determined by preserving the longest common subsequence between them. Because the second array is sorted and contains distinct elements, the LCS problem can be transformed into a Longest Increasing Subsequence problem by mapping elements to their indices. This optimization reduces the overall time complexity from O(n × m) to O(n log n), making the solution efficient for large input sizes.