2111. 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:

  • 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 K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[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 K-increasing for the given k.

class Solution {
    vector<int> LIS;
    int lis(vector<int>& arr, int i, int& k) {
        LIS.clear();
        for(;i < arr.size(); i += k) {
            if(LIS.empty() or LIS.back() <= arr[i])
                LIS.push_back(arr[i]);
            else
                *upper_bound(LIS.begin(), LIS.end(), arr[i]) = arr[i];
        }
        
        return LIS.size();
    }
public:
    int kIncreasing(vector<int>& arr, int k) {
        int sum = 0, n = arr.size();
        for(int st = 0; st < k; st++) {
            sum += lis(arr,st,k);
        }
        return n - sum;
    }
};