LIS: 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))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store