1713. Minimum operations to make a subsequence

link

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.
In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.
Return the minimum number of operations needed to make target a subsequence of arr.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

1. Attempt 1

Notice numbers in arr does not matter unless it is contained in target. Example

target = [5,1,3], arr = [9,4,2,3,4]

can be simplified to

target = [5,1,3], arr = [3]

So this is an edit distance question with only insertion enabled. See the next subsection for a review of editing distance.

Follow the editing distance way of thinking, define state = dp[i,j] as operations to make target[0,i] be a sub-sequence of arr[0,j]

When target[i] == target[j]: dp[i,j] = dp[i-1,j-1]

When target[i] == target[j]:

1. Option 1: do insertion:

   target = [5,7,3], i = 2
   arr = [1,5,7], j = 2
   

   insert 3 to arr. This means dp[i,j] = dp[i-1,j]+1
2. Option 2: do nothing:

   target = [1,5,7], i = 2
   arr = [5,7,3], j = 2;
   

Ignore the 3 at arr[j]. This means dp[i,j] = dp[i, j-1]

Thus

dp[i,j] = 
    dp[i-1,j-1]                      when target[i] == target[j]; OR
    Math.min(dp[i,j-1], dp[i-1,j]+1) when target[i] != target[j].

Complexity O(mn), O(min(m, n)). TLE.

class Solution {
    private static record State(int i, int j){};
    public int minOperations(int[] target, int[] arr) {
        return helper(target.length-1, arr.length-1, 
                      new HashMap<>(), target, arr);
    }

    private int helper(int i, int j, 
                       Map<State, Integer> mem, 
                       int[] target, int[] arr) {
        if(i == -1) return 0;
        if(j == -1) return i+1;
        if(mem.containsKey(state)) return mem.get(new State(i,j));
        int res = 0;
        if(target[i] == arr[j]) res = helper(i-1, j-1, mem, target, arr);
        else res = Math.min(helper(i-1, j, mem, target, arr) + 1, 
                            helper(i, j-1, mem, target, arr));
        mem.put(new State(i,j), res);
        return res;
    }
}

1.1 Editing distance:

Try to make str1 same as str2. Define state
dp[i,j] as the editing distance between str1.substring[0,i] and str2.substring[0,j]:

When str1[i] == str2[j]:

dp[i,j] = dp[i-1,j-1] + 1. simple enough.

When str1[i] != str2[j]:

Example:

1. Option 1: replace:

   str1 = "abc", i = 2
   str2 = "abd", j = 2
   

   replace c with d, then dp[i,j] = dp[i-1,j-1] + 1
2. Option 2: delete

   str1 = "abc", i = 2
   str2 = "aab", j = 2
   

   delete c. then dp[i,j] = dp[i-1, j] + 1
3. Option 3: insertion

   str1 = "caa", i = 2
   str2 = "aab", j = 2
   

   insert a b at the end of str1. so dp[i,j] = dp[i, j-1] + 1
   Thus
   dp[i,j] = min(dp[i-1,j-1], dp[i,j-1], dp[i-1,j]) + 1

2. Attempt 2

Hint 1: The problem can be reduced to computing Longest Common Subsequence between both arrays.

Minimum insertions = target.length() - longest common subsequence(target, arr)
So it simplified to LCS. LCS state transfer equation:

dp[i, j] = 
  dp[i-1, j-1] + 1, if target[i] == arr[j]; OR
  Math.max(dp[i-1, j], dp[i, j-1]), if target[i] != arr[j]

same complexity. still TLE.

3. Attempt 3

question says:

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

Thus hint 2

Since one of the arrays has distinct elements, we can consider that these elements describe an arrangement of numbers, and we can replace each element in the other array with the index it appeared at in the first array.
Then the problem is converted to finding Longest Increasing Subsequence in the second array, which can be done in O(n log n).

LIS. LIS of an array.
A simple O(n^2) solution

dp[i] = Math.max(dp[k]) + 1, where arr[k] < arr[i] and k < i. 
edge: if no such k. then set dp[i] = 0

3.1 LIS using sequence building method: O(n^2)

See approach 2.

Given [5,7,9,8,2,3,4,8,1] LIS can be built as

1. Get 5, put it in result sequence [5]
2. Get 7, larger than result sequence largest. Update result to [5,7]
3. Get 9, update to [5,7,9]
4. Get 8, smaller than result sequence largest, but if update 9 to 8 opens up some possibilities. Thus update result to [5,7,8]
5. Get 2, better than 5, so update result to [2,7,8]
6. Get 3, replace 7 with 3, result [2,3,8]
7. Get 4, replace 8 with 4, result [2,3,4]
8. Get 8, append to end. result [2,3,4,8]
9. Get 1, replace 2 with 1. result [1,3,4,8]

This way we find the LIS has to be length 4.

Note This method does not guarantee the result sequence is a valid sequence. Only length is correct. The result [1,3,4,8] is not a valid sequence.

This method is basically saying we build a monotonically increasing result array. Each incoming element, find the first one that is equal or larger than self, replace self with that element.

3.2 Optimized LIS using sequence building and binary search: O(nlogn)

Method 3.1 has that monotonically increasing sequence. So finding the first one that is equal or larger can be done via binary search. Algorithm can be further simplified to O(nlogn).

Now going back to the original 1713 question, this question can thus be solved in O(nlogn).