{"id":7901,"date":"2021-01-03T11:57:02","date_gmt":"2021-01-03T19:57:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7901"},"modified":"2021-01-09T16:38:46","modified_gmt":"2021-01-10T00:38:46","slug":"leetcode-1713-minimum-operations-to-make-a-subsequence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1713-minimum-operations-to-make-a-subsequence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1713. Minimum Operations to Make a Subsequence"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u3010LCS\/LIS\u3011\u82b1\u82b1\u9171 LeetCode 1713. Minimum Operations to Make a Subsequence - \u5237\u9898\u627e\u5de5\u4f5c EP379\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/5vBPESNPEu4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given an array&nbsp;<code>target<\/code>&nbsp;that consists of&nbsp;<strong>distinct<\/strong>&nbsp;integers and another integer array&nbsp;<code>arr<\/code>&nbsp;that&nbsp;<strong>can<\/strong>&nbsp;have duplicates.<\/p>\n\n\n\n<p>In one operation, you can insert any integer at any position in&nbsp;<code>arr<\/code>. For example, if&nbsp;<code>arr = [1,4,1,2]<\/code>, you can add&nbsp;<code>3<\/code>&nbsp;in the middle and make it&nbsp;<code>[1,4,<u>3<\/u>,1,2]<\/code>. Note that you can insert the integer at the very beginning or end of the array.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of operations needed to make&nbsp;<\/em><code>target<\/code><em>&nbsp;a&nbsp;<strong>subsequence<\/strong>&nbsp;of&nbsp;<\/em><code>arr<\/code><em>.<\/em><\/p>\n\n\n\n<p>A&nbsp;<strong>subsequence<\/strong>&nbsp;of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements&#8217; relative order. For example,&nbsp;<code>[2,7,4]<\/code>&nbsp;is a subsequence of&nbsp;<code>[4,<u>2<\/u>,3,<u>7<\/u>,2,1,<u>4<\/u>]<\/code>&nbsp;(the underlined elements), while&nbsp;<code>[2,4,2]<\/code>&nbsp;is not.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> target = [5,1,3], <code>arr<\/code> = [9,4,2,3,4]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> You can add 5 and 1 in such a way that makes <code>arr<\/code> = [5,9,4,1,2,3,4], then target will be a subsequence of <code>arr<\/code>.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> target = [6,4,8,1,3,2], <code>arr<\/code> = [4,7,6,2,3,8,6,1]\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= target.length, arr.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= target[i], arr[i] &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>target<\/code>&nbsp;contains no duplicates.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Reduce to LIS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-1.png\" alt=\"\" class=\"wp-image-7942\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-2.png\" alt=\"\" class=\"wp-image-7943\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/01\/1713-ep379-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.<br>Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.<\/p>\n\n\n\n<p>e.g. <br>target: [6,4,8,1,3,2] =&gt; [0, 1, 2, 3, 4, 5]<br>array: [4,7,6,2,3,8,6,1] =&gt; [1,-1, 0, 5, 4, 2, 0, 3] =&gt; [1, 0, 5, 4, 2, 3]<br>and the LIS is [0, 2, 3] =&gt; [6, 8, 1], we need to insert the rest of the numbers.<br>Ans = len(target) &#8211; len(LIS)<\/p>\n\n\n\n<p>Time complexity: O(nlogm)<br>Space complexity: O(m)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minOperations(vector<int>& A, vector<int>& B) {\n    unordered_map<int, int> m;\n    for (int i = 0; i < A.size(); ++i)\n      m[A[i]] = i;\n    vector<int> dp;\n    for (int x : B) {\n      auto mit = m.find(x);\n      if (mit == end(m)) continue;\n      const int idx = mit->second;\n      if (dp.empty() || idx > dp.back())\n        dp.push_back(idx);\n      else\n        *lower_bound(begin(dp), end(dp), idx) = idx;\n    }\n    return A.size() - dp.size();\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:  \n  def minOperations(self, A: List[int], B: List[int]) -> int:\n    m = {x: i for i, x in enumerate(A)}\n    dp = []\n    for x in B:\n      if x not in m: continue\n      if not dp or m[x] > dp[-1]: dp.append(m[x])\n      else: dp[bisect_left(dp, m[x])] = m[x]\n    return len(A) - len(dp)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><br><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;target&nbsp;that consists of&nbsp;distinct&nbsp;integers and another integer array&nbsp;arr&nbsp;that&nbsp;can&nbsp;have duplicates. In one operation, you can insert any integer at any position in&nbsp;arr. For&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,66,69],"class_list":["post-7901","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-lcs","tag-lis","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7901","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7901"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7901\/revisions"}],"predecessor-version":[{"id":7945,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7901\/revisions\/7945"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7901"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7901"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7901"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}