Minimum Insert and Delete to Convert

Problem Overview

Convert array a into b using only deletions from a and insertions into a (no replacements).

Intuition

Convert array a into b using only deletions from a and insertions into a (no replacements). Elements kept in order form a common subsequence; maximize its length L. Delete |a| − L unmatched elements from a and insert |b| − L missing elements — total |a| + |b| − 2L.

Algorithm

1Map each value in b to its index (assume distinct or use positions as in problem).
2Scan a: append b-index for values that appear in b to a list.
3Compute LIS length on that list — equals LCS length in O(n log n).
4Return (a.length − L) + (b.length − L).

Example Walkthrough

Input: a = [4, 1, 3, 2], b = [1, 3, 4, 2]

1. Common subsequence {1, 3, 2} has length 3.
2. Delete 4 from a (1 op), insert 4 into position (1 op) → total 2.

Output: 2

Common Pitfalls

• Only insert/delete — reduce to LCS, not full edit distance.
• LIS on mapped indices works when matching value equality in order.
• Elements of a not in b must be deleted — they never enter the list.

Minimum Insert and Delete to Convert.java

Java

// Approach: Min insert + delete = |a| + |b| − 2·LCS(a, b). Map b values to indices, scan a into
// that index sequence, and compute LIS length in O(n log n) — equals LCS length.
// Time: O(n log n) Space: O(n)

import java.util.*;

class Solution {

    public int minInsAndDel(int[] a, int[] b) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < b.length; i++) {
            map.put(b[i], i);
        }

        ArrayList<Integer> list = new ArrayList<>();

        for (int x : a) {
            if (map.containsKey(x)) {
                list.add(map.get(x));
            }
        }

        ArrayList<Integer> lis = new ArrayList<>();

        for (int x : list) {
            int idx = Collections.binarySearch(lis, x);

            if (idx < 0) {
                idx = -(idx + 1);
            }

            if (idx == lis.size()) {
                lis.add(x);
            } else {
                lis.set(idx, x);
            }
        }

        int common = lis.size();

        return (a.length - common) + (b.length - common);
    }
}

Was this solution helpful?