Problem Statement

You are given two arrays:

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:

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

(n − L) + (m − L)

Correctness Proof

Let L be the length of the Longest Increasing Subsequence of the mapped index array.

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

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.