2111. Minimum Operations to Make the Array K-Increasing LeetCode Solution
In this guide, you will get 2111. Minimum Operations to Make the Array K-Increasing LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Make the Array K-Increasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Operations to Make the Array K-Increasing
You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k.
The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1.
For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because:
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 K-increasing 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 non-decreasing.
Some of the K-increasing 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 K-increasing in less than 4 operations.
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[i-2] <= arr[i].
Since the given array is already K-increasing, 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[i-3] <= arr[i] for 3 <= i <= 5.
One of the ways we can make the array K-increasing 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 K-increasing, but none of them require less than 2 operations.
2111. Minimum Operations to Make the Array K-Increasing LeetCode Solution in C++
class Solution {
public:
int kIncreasing(vector<int>& arr, int k) {
int ans = 0;
for (int i = 0; i < k; ++i) {
vector<int> arr;
for (int j = i; j < arr.size(); j += k)
arr.push_back(arr[j]);
ans += numReplaced(arr);
}
return ans;
}
private:
int numReplaced(const vector<int>& arr) {
vector<int> tails;
for (const int a : arr)
if (tails.empty() || tails.back() <= a)
tails.push_back(a);
else
tails[firstGreater(tails, a)] = a;
return arr.size() - tails.size();
}
int firstGreater(const vector<int>& arr, int target) {
return ranges::upper_bound(arr, target) - arr.begin();
}
}; /* code provided by PROGIEZ */
2111. Minimum Operations to Make the Array K-Increasing LeetCode Solution in Java
class Solution {
public int kIncreasing(int[] arr, int k) {
int ans = 0;
for (int i = 0; i < k; ++i) {
List<Integer> arr = new ArrayList<>();
for (int j = i; j < arr.length; j += k)
arr.add(arr[j]);
ans += numReplaced(arr);
}
return ans;
}
private int numReplaced(List<Integer> arr) {
List<Integer> tails = new ArrayList<>();
for (final int a : arr)
if (tails.isEmpty() || tails.get(tails.size() - 1) <= a)
tails.add(a);
else
tails.set(firstGreater(tails, a), a);
return arr.size() - tails.size();
}
private int firstGreater(List<Integer> arr, int target) {
final int i = Collections.binarySearch(arr, target + 1);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
2111. Minimum Operations to Make the Array K-Increasing LeetCode Solution in Python
class Solution:
def kIncreasing(self, arr: list[int], k: int) -> int:
def numReplaced(arr: list[int]) -> int:
tails = []
for a in arr:
if not tails or tails[-1] <= a:
tails.append(a)
else:
tails[bisect_right(tails, a)] = a
return len(arr) - len(tails)
return sum(numReplaced(arr[i::k]) for i in range(k)) # code by PROGIEZ
