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

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Running the SAM CLI on Linux

Preparing the Dart and Flutter ecosystem for null safety

| Engineering News-Record

How We Upgraded Rails Safely

A backhoe working in a neighborhood next to a statue, safety cones, and a person parking their bike

How to create a simple Hangman game with Python

Does Text Preprocessing Affect Natural Language Processing Performance?

Website development isn’t much harder than Word documents. Here’s how.

Sort a string in java without using Arrays.so

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
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Leetcode 452. Minimum Number of Arrows to Burst Balloons

[Leet Code] Maximum Number of Words Found in Sentences

Binary Tree Path Sum(code and Explanation)

Data Structure — Linked List