Leetcode 1713. Minimum Operations to Make a Subsequence

Problem Explanation

We are given an array target containing distinct integers and another array arr which can have duplicate integers. Our goal is to perform the least number of operations, an operation being inserting an integer at any position in arr. We want to achieve a situation where target is a subsequence of arr.

A subsequence is a new array formed from the original array by deleting some or no elements and not changing the remaining elements' relative order.

Example Walk-through

Consider the following example: target = [5,1,3] arr = [9,4,2,3,4]

The output should be 2. To achieve a subsequence, we need to insert 5 and 1 in arr in such a way that it becomes [5,9,4,1,2,3,4]. Now, the target becomes the subsequence of arr.

Solution Approach

The problem can be approached by finding the Longest Common Subsequence (LCS) in the target and arr. We need to find a position-map, which is the position of elements in the target array. Now, we find the lower bound of elements in position of arr, thus finding the minimum number of operations needed.

Let's demonstrate the approach with an example:

target = [6,4,8,1,3,2] arr = [4,7,6,2,3,8,6,1]

Create a position-map for target: {6: 0, 4: 1, 8: 2, 1: 3, 3: 4, 2: 5}

Now, find the lower bound for elements in the position of arr [1, 0, 5, 4, 2, 0, 3], which is [1, 0, 2, 0].

We can now calculate the minimum operations: len(target) - len(lcs) = 6 - 3 = 3

Solution in Python

1import bisect
2
3class Solution:
4    def minOperations(self, target: List[int], arr: List[int]) -> int:
5        pos = {num: i for i, num in enumerate(target)}
6
7        lower_bound = []
8        
9        for num in arr:
10            if num in pos:
11                idx = bisect.bisect_left(lower_bound, pos[num])
12                if len(lower_bound) == idx:
13                    lower_bound.append(pos[num])
14                else:
15                    lower_bound[idx] = pos[num]
16
17        return len(target) - len(lower_bound)

Solution in Java

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    public int minOperations(int[] target, int[] arr) {
8
9        Map<Integer, Integer> pos = new HashMap<>();
10        for (int i = 0; i < target.length; i++) {
11            pos.put(target[i], i);
12        }
13        List<Integer> lowerBound = new ArrayList<>();
14
15        for (int num : arr) {
16            if (pos.containsKey(num)) {
17                int idx = lowerBound(lowerBound, pos.get(num));
18                if (lowerBound.size() == idx) {
19                    lowerBound.add(pos.get(num));
20                } else {
21                    lowerBound.set(idx, pos.get(num));
22                }
23            }
24        }
25        
26        return target.length - lowerBound.size();
27    }
28    
29    private int lowerBound(List<Integer> loc, int num) {
30        int left = 0;
31        int right = loc.size();
32
33        while (left < right) {
34            int mid = left + (right - left) / 2;
35            if (loc.get(mid) >= num) {
36                right = mid;
37            } else {
38                left = mid + 1;
39            }
40        }
41        
42        return left;
43    }
44}

Solution in JavaScript

1'use strict';
2
3var bisect_left = function(arr, item) {
4    let low = 0,
5        high = arr.length;
6    while (low < high) {
7        let mid = (low + high) >> 1;
8        if (arr[mid] < item) low = mid + 1;
9        else high = mid;
10    }
11    return low;
12};
13
14var Solution = {
15    minOperations: function(target, arr) {
16        const pos = new Map();
17        
18        for (let i = 0; i < target.length; i++) {
19            pos.set(target[i], i);
20        }
21        
22        const lower_bound = [];
23        
24        for (let num of arr) {
25            if (pos.has(num)) {
26                let idx = bisect_left(lower_bound, pos.get(num));
27                if (idx == lower_bound.length) {
28                    lower_bound.push(pos.get(num));
29                } else {
30                    lower_bound[idx] = pos.get(num);
31                }
32            }
33        }
34        
35        return target.length - lower_bound.length;
36    }
37};

Solution in C++

1#include <bits/stdc++.h>
2
3class Solution {
4public:
5    int minOperations(vector<int>& target, vector<int>& arr) {
6
7        unordered_map<int, int> pos;
8        for (int i = 0; i < target.size(); i++) {
9            pos[target[i]] = i;
10        }
11        
12        vector<int> lower_bound;
13        
14        for (int num : arr) {
15            if (pos.count(num)) {
16                auto it = lower_bound(pos[num]);
17                if (it == lower_bound.end()) {
18                    lower_bound.push_back(pos[num]);
19                } else {
20                    *it = pos[num];
21                }
22            }
23        }
24        
25        return target.size() - lower_bound.size();
26    }
27
28    vector<int>::iterator lower_bound(vector<int>& loc, int num) {
29
30        return std::lower_bound(loc.begin(), loc.end(), num);
31    }
32};

Solution in C#

1using System;
2using System.Collections.Generic;
3
4public class Solution
5{
6    public int MinOperations(int[] target, int[] arr)
7    {
8        Dictionary<int, int> pos = new Dictionary<int, int>();
9        for (int i = 0; i < target.Length; ++i)
10        {
11            pos[target[i]] = i;
12        }
13        
14        List<int> lower_bound = new List<int>();
15        
16        foreach (int num in arr) {
17            if (pos.ContainsKey(num)) {
18                int idx = LowerBound(lower_bound, pos[num]);
19                if (lower_bound.Count == idx)
20                {
21                    lower_bound.Add(pos[num]);
22                }
23                else {
24                    lower_bound[idx] = pos[num];
25                }
26            }
27        }
28        
29        return target.Length - lower_bound.Count;
30    }
31
32    private int LowerBound(List<int> loc, int num)
33    {
34        int left = 0;
35        int right = loc.Count;
36
37        while (left < right)
38        {
39            int mid = left + (right - left) / 2;
40            if (loc[mid] >= num)
41            {
42                right = mid;
43            }
44            else {
45                left = mid + 1;
46            }
47        }
48        return left;
49    }
50}

In summary, given an array target containing distinct integers and another array arr, the goal is to calculate the least number of operations required for target to be a subsequence of arr. The problem can be solved using the Longest Common Subsequence approach, which requires creating a position-map for the target array and then finding the lower bound. The solutions provided are in Python, Java, JavaScript, C++, and C#.