Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2111.html
2111. Minimum Operations to Make the Array KIncreasing (Hard)
You are given a 0indexed array arr
consisting of n
positive integers, and a positive integer k
.
The array arr
is called Kincreasing if arr[ik] <= arr[i]
holds for every index i
, where k <= i <= n1
.
 For example,
arr = [4, 1, 5, 2, 6, 2]
is Kincreasing fork = 2
because:arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
 However, the same
arr
is not Kincreasing fork = 1
(becausearr[0] > arr[1]
) ork = 3
(becausearr[0] > arr[3]
).
In one operation, you can choose an index i
and change arr[i]
into any positive integer.
Return the minimum number of operations required to make the array Kincreasing for the given k
.
Example 1:
Input: arr = [5,4,3,2,1], k = 1 Output: 4 Explanation: For k = 1, the resultant array has to be nondecreasing. Some of the Kincreasing arrays that can be formed are [5,6,7,8,9], [1,1,1,1,1], [2,2,3,4,4]. All of them require 4 operations. It is suboptimal to change the array to, for example, [6,7,8,9,10] because it would take 5 operations. It can be shown that we cannot make the array Kincreasing in less than 4 operations.
Example 2:
Input: arr = [4,1,5,2,6,2], k = 2 Output: 0 Explanation: This is the same example as the one in the problem description. Here, for every index i where 2 <= i <= 5, arr[i2] <= arr[i]. Since the given array is already Kincreasing, we do not need to perform any operations.
Example 3:
Input: arr = [4,1,5,2,6,2], k = 3 Output: 2 Explanation: Indices 3 and 5 are the only ones not satisfying arr[i3] <= arr[i] for 3 <= i <= 5. One of the ways we can make the array Kincreasing is by changing arr[3] to 4 and arr[5] to 5. The array will now be [4,1,5,4,6,5]. Note that there can be other ways to make the array Kincreasing, but none of them require less than 2 operations.
Constraints:
1 <= arr.length <= 10^{5}
1 <= arr[i], k <= arr.length
Similar Questions:
Solution 1. Longest Increasing Subsequence (LIS)
Split the numbers in A
into k
groups: [0, k, 2k, 3k, ...]
, [1, 1+k, 1+2k, 1+3k, ...]
, …
Compute the minimum operations needed to make a group nondecreasing. Assume the Longest Increasing Subsequence (LIS) of this group is of length t
, and the group is of length len
, then the minimum operations needed is len  t
.
Computing the length of LIS is a classic problem that can be solved using binary search. See 300. Longest Increasing Subsequence (Medium)
The answer is the sum of minimum operations for all the groups.

// OJ: https://leetcode.com/problems/minimumoperationstomakethearraykincreasing/ // Time: O(Nlog(N/k)) // Space: O(N/k) class Solution { public: int kIncreasing(vector<int>& A, int k) { int N = A.size(), ans = 0; for (int i = 0; i < k; ++i) { // handle each group separately vector<int> lis{A[i]}; // the longest nondecreasing subsequence of this group int len = 1; // the length of this group for (int j = i + k; j < N; j += k, ++len) { auto i = upper_bound(begin(lis), end(lis), A[j]); if (i == end(lis)) lis.push_back(A[j]); else *i = A[j]; } ans += len  lis.size(); } return ans; } };

// Todo

class Solution: def kIncreasing(self, arr: List[int], k: int) > int: def lis(arr): t = [] for x in arr: idx = bisect_right(t, x) if idx == len(t): t.append(x) else: t[idx] = x return len(arr)  len(t) return sum(lis(arr[i::k]) for i in range(k)) ############ # 2111. Minimum Operations to Make the Array KIncreasing # https://leetcode.com/problems/minimumoperationstomakethearraykincreasing/ class Solution: def kIncreasing(self, arr: List[int], k: int) > int: A = collections.defaultdict(list) for i, x in enumerate(arr): A[i % k].append(x) res = 0 for _, s in A.items(): lis = [] for x in s: index = bisect.bisect(lis, x) if index < len(lis): lis[index] = x else: lis.append(x) res += len(s)  len(lis) return res
Discuss
https://leetcode.com/problems/minimumoperationstomakethearraykincreasing/discuss/1634980/C%2B%2BLongestIncreasingSubsequence