{"id":9193,"date":"2021-12-22T11:55:14","date_gmt":"2021-12-22T19:55:14","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9193"},"modified":"2021-12-22T12:04:42","modified_gmt":"2021-12-22T20:04:42","slug":"leetcode-2111-minimum-operations-to-make-the-array-k-increasing","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2111-minimum-operations-to-make-the-array-k-increasing\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2111. Minimum Operations to Make the Array K-Increasing"},"content":{"rendered":"\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;array&nbsp;<code>arr<\/code>&nbsp;consisting of&nbsp;<code>n<\/code>&nbsp;positive integers, and a positive integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>The array&nbsp;<code>arr<\/code>&nbsp;is called&nbsp;<strong>K-increasing<\/strong>&nbsp;if&nbsp;<code>arr[i-k] &lt;= arr[i]<\/code>&nbsp;holds for every index&nbsp;<code>i<\/code>, where&nbsp;<code>k &lt;= i &lt;= n-1<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example,&nbsp;<code>arr = [4, 1, 5, 2, 6, 2]<\/code>&nbsp;is K-increasing for&nbsp;<code>k = 2<\/code>&nbsp;because:<ul><li><code>arr[0] &lt;= arr[2] (4 &lt;= 5)<\/code><\/li><li><code>arr[1] &lt;= arr[3] (1 &lt;= 2)<\/code><\/li><li><code>arr[2] &lt;= arr[4] (5 &lt;= 6)<\/code><\/li><li><code>arr[3] &lt;= arr[5] (2 &lt;= 2)<\/code><\/li><\/ul><\/li><li>However, the same&nbsp;<code>arr<\/code>&nbsp;is not K-increasing for&nbsp;<code>k = 1<\/code>&nbsp;(because&nbsp;<code>arr[0] &gt; arr[1]<\/code>) or&nbsp;<code>k = 3<\/code>&nbsp;(because&nbsp;<code>arr[0] &gt; arr[3]<\/code>).<\/li><\/ul>\n\n\n\n<p>In one&nbsp;<strong>operation<\/strong>, you can choose an index&nbsp;<code>i<\/code>&nbsp;and&nbsp;<strong>change<\/strong>&nbsp;<code>arr[i]<\/code>&nbsp;into&nbsp;<strong>any<\/strong>&nbsp;positive integer.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum number of operations<\/strong>&nbsp;required to make the array K-increasing for the given&nbsp;<\/em><code>k<\/code>.<\/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> arr = [5,4,3,2,1], k = 1\n<strong>Output:<\/strong> 4\n<strong>Explanation:\n<\/strong>For k = 1, the resultant array has to be non-decreasing.\nSome of the K-increasing arrays that can be formed are [5,<strong>6<\/strong>,<strong>7<\/strong>,<strong>8<\/strong>,<strong>9<\/strong>], [<strong>1<\/strong>,<strong>1<\/strong>,<strong>1<\/strong>,<strong>1<\/strong>,1], [<strong>2<\/strong>,<strong>2<\/strong>,3,<strong>4<\/strong>,<strong>4<\/strong>]. All of them require 4 operations.\nIt is suboptimal to change the array to, for example, [<strong>6<\/strong>,<strong>7<\/strong>,<strong>8<\/strong>,<strong>9<\/strong>,<strong>10<\/strong>] because it would take 5 operations.\nIt can be shown that we cannot make the array K-increasing in less than 4 operations.\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> arr = [4,1,5,2,6,2], k = 2\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong>\nThis is the same example as the one in the problem description.\nHere, for every index i where 2 &lt;= i &lt;= 5, arr[i-2] &lt;=arr[i].\nSince the given array is already K-increasing, we do not need to perform any operations.<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [4,1,5,2,6,2], k = 3\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong>\nIndices 3 and 5 are the only ones not satisfying arr[i-3] &lt;= arr[i] for 3 &lt;= i &lt;= 5.\nOne of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5.\nThe array will now be [4,1,5,<strong>4<\/strong>,6,<strong>5<\/strong>].\nNote that there can be other ways to make the array K-increasing, but none of them require less than 2 operations.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= arr[i], k &lt;= arr.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Longest increasing subsequence<\/strong><\/h2>\n\n\n\n<p>if k = 1, <meta charset=\"utf-8\">we need to modify the following arrays<br>1. [a[0], a[1], a[2], &#8230;]<br>if k = 2, <meta charset=\"utf-8\">we need to modify the following arrays<br>1. <meta charset=\"utf-8\">[a[0], a[2], a[4], &#8230;]<br>2. [a[1], a[3], a[5], &#8230;]<br>if k = 3, we need to modify the following arrays<br><meta charset=\"utf-8\">1. <meta charset=\"utf-8\">[a[0], a[3], a[6], &#8230;]<br>2. [a[1], a[4], a[7], &#8230;]<br>3. <meta charset=\"utf-8\">[a[2], a[5], a[8], &#8230;]<br>&#8230;<\/p>\n\n\n\n<p>These arrays are independent of each other, we just need to find LIS of it, # ops = len(arr) &#8211; LIS(arr).<br>Ans = sum(len(arr<sub>i<\/sub>) &#8211; LIS(arr<sub>i<\/sub>))  1 &lt;= i &lt;= k<\/p>\n\n\n\n<p>Reference: <a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-300-longest-increasing-subsequence\/\" data-type=\"post\" data-id=\"206\">\u82b1\u82b1\u9171 LeetCode 300. Longest Increasing Subsequence<\/a><\/p>\n\n\n\n<p>Time complexity: O(k * (n\/k)* log(n\/k)) = O(n * log(n\/k))<br>Space complexity: O(n\/k)<\/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 kIncreasing(vector<int>& arr, int k) {\n    auto LIS = [](const vector<int>& nums) {\n      vector<int> lis;\n      for (int x : nums)\n        if (lis.empty() || lis.back() <= x)\n          lis.push_back(x);\n        else\n          *upper_bound(begin(lis), end(lis), x) = x;\n      return lis.size();\n    };\n    const int n = arr.size();\n    int ans = 0;\n    for (int i = 0; i < k; ++i) {\n      vector<int> cur;\n      for (int j = i; j < n; j += k)\n        cur.push_back(arr[j]);\n      ans += cur.size() - LIS(cur);\n    }\n    return ans;\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 kIncreasing(self, arr: List[int], k: int) -> int:\n    def LIS(arr: List[int]) -> int:\n      lis = []\n      for x in arr:\n        if not lis or lis[-1] <= x:\n          lis.append(x)\n        else:\n          lis[bisect_right(lis, x)] = x\n      return len(lis)\n    \n    return sum(len(arr[i::k]) - LIS(arr[i::k]) for i in range(k))\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;array&nbsp;arr&nbsp;consisting of&nbsp;n&nbsp;positive integers, and a positive integer&nbsp;k. The array&nbsp;arr&nbsp;is called&nbsp;K-increasing&nbsp;if&nbsp;arr[i-k] &lt;= arr[i]&nbsp;holds for every index&nbsp;i, where&nbsp;k &lt;= i &lt;= n-1. For example,&nbsp;arr&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[20,52,217,69],"class_list":["post-9193","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-array","tag-binary-search","tag-hard","tag-lis","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9193","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=9193"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9193\/revisions"}],"predecessor-version":[{"id":9198,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9193\/revisions\/9198"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}