LIS: minimum operations to make the array K-increasing

2111. Minimum Operations to Make the Array K-Increasing

This is the 4th problem of this week’s LC weekly contest.

Explanation

We can change the problem to find the LIS for each subsequence with index of

• 0, k, 2k, …
• 1, k+1, k + 1 + k,…

A well know problem of longest increasing or non decreasing subsqeuence problem. By using “straightforward” DP, the complexity is O(n²). We do have a O(n log k) solution.

We can is independent to consider subproblems on 0, k, 2k, ..., 1, k+1, 2k+1, ... and so on.

C++ code

class Solution {
    public:
    int lis(vector<int>& nums){ // n log k complexity where k is the longest non decreasing subsequence length
        const int n = nums.size();
        vector<int> LIS(n, 0);
        int k =0, ret = 0;
        for (int i = 0; i < n; ++i) {
            auto pos = upper_bound(LIS.begin(), LIS.begin()+k, nums[i])-LIS.begin();
            LIS[pos] = nums[i];
            if (pos==k) k = pos + 1;
            ret = max(ret, k);
        }
        return ret; 
    } 
    int kIncreasing(vector<int>& nums, int k) {
        const int n = nums.size();
        int total_lis_len = 0;
        for (int i = 0; i < k; ++i){
            vector<int> this_nums;
            for (int j = i; j < n; j += k){
                this_nums.push_back(nums[j]);
            }
            total_lis_len += lis(this_nums);
        }
        return n - total_lis_len;
    }    
};

Python Code

INF = 1000000000
class Solution:
    def lis(self, a):
        non_decrease_sequence = [INF]*(len(a) + 1)
        for e in a:
            idx = bisect.bisect(non_decrease_sequence, e)
            non_decrease_sequence[idx] = e
        return non_decrease_sequence.index(INF)
        
    def kIncreasing(self, arr: List[int], k: int) -> int:
        return len(arr) - sum(self.lis(arr[begin_idx::k]) for begin_idx in range(k))