Minimum Operations to Make the Array K-Increasing
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 fork = 2because: 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
arris not K-increasing fork = 1(becausearr[0] > arr[1]) ork = 3(becausearr[0] > arr[3]).
- However, the same
In one operation , you can choose an index i and change arr[i]
into any positive integer.
Return _theminimum number of operations required to make the array K-increasing for the given _k.
Examples
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.
Example 2
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.
Constraints
1 <= arr.length <= 10^51 <= arr[i], k <= arr.length
Solution
Method 1 – Longest Non-Decreasing Subsequence (LNDS) by Groups
Intuition
The array can be split into k groups, each group containing elements at positions i, i+k, i+2k, etc. Each group must be non-decreasing for the whole array to be k-increasing. The minimum number of changes for each group is the group size minus the length of its longest non-decreasing subsequence.
Approach
- For each group (from 0 to k-1), collect elements at indices i, i+k, i+2k, ...
- For each group, compute the length of the longest non-decreasing subsequence (LNDS) using binary search.
- The number of changes for the group is its size minus LNDS length.
- Sum changes for all groups to get the answer.
- Edge case: If the array is already k-increasing, answer is 0.
Code
C++
class Solution {
public:
int minOperations(vector<int>& arr, int k) {
int n = arr.size(), ans = 0;
for (int i = 0; i < k; ++i) {
vector<int> seq;
for (int j = i; j < n; j += k) seq.push_back(arr[j]);
vector<int> dp;
for (int x : seq) {
auto it = upper_bound(dp.begin(), dp.end(), x);
if (it == dp.end()) dp.push_back(x);
else *it = x;
}
ans += seq.size() - dp.size();
}
return ans;
}
};
Go
func minOperations(arr []int, k int) int {
n, ans := len(arr), 0
for i := 0; i < k; i++ {
seq := []int{}
for j := i; j < n; j += k {
seq = append(seq, arr[j])
}
dp := []int{}
for _, x := range seq {
idx := sort.Search(len(dp), func(i int) bool { return dp[i] > x })
if idx == len(dp) {
dp = append(dp, x)
} else {
dp[idx] = x
}
}
ans += len(seq) - len(dp)
}
return ans
}
Java
class Solution {
public int minOperations(int[] arr, int k) {
int n = arr.length, ans = 0;
for (int i = 0; i < k; i++) {
List<Integer> seq = new ArrayList<>();
for (int j = i; j < n; j += k) seq.add(arr[j]);
List<Integer> dp = new ArrayList<>();
for (int x : seq) {
int idx = Collections.binarySearch(dp, x + 1);
if (idx < 0) idx = -idx - 1;
if (idx == dp.size()) dp.add(x);
else dp.set(idx, x);
}
ans += seq.size() - dp.size();
}
return ans;
}
}
Kotlin
class Solution {
fun minOperations(arr: IntArray, k: Int): Int {
var ans = 0
for (i in 0 until k) {
val seq = mutableListOf<Int>()
var j = i
while (j < arr.size) {
seq.add(arr[j])
j += k
}
val dp = mutableListOf<Int>()
for (x in seq) {
val idx = dp.binarySearch(x + 1).let { if (it < 0) -it - 1 else it }
if (idx == dp.size) dp.add(x) else dp[idx] = x
}
ans += seq.size - dp.size
}
return ans
}
}
Python
class Solution:
def minOperations(self, arr: list[int], k: int) -> int:
ans = 0
n = len(arr)
for i in range(k):
seq = [arr[j] for j in range(i, n, k)]
dp = []
for x in seq:
idx = bisect.bisect_right(dp, x)
if idx == len(dp):
dp.append(x)
else:
dp[idx] = x
ans += len(seq) - len(dp)
return ans
Rust
impl Solution {
pub fn min_operations(arr: Vec<i32>, k: i32) -> i32 {
let n = arr.len();
let mut ans = 0;
for i in 0..k {
let mut seq = vec![];
let mut j = i as usize;
while j < n {
seq.push(arr[j]);
j += k as usize;
}
let mut dp: Vec<i32> = vec![];
for &x in &seq {
let idx = dp.binary_search_by(|v| if *v > x { std::cmp::Ordering::Greater } else { std::cmp::Ordering::Less }).unwrap_or_else(|x| x);
if idx == dp.len() {
dp.push(x);
} else {
dp[idx] = x;
}
}
ans += seq.len() as i32 - dp.len() as i32;
}
ans
}
}
TypeScript
class Solution {
minOperations(arr: number[], k: number): number {
let ans = 0;
const n = arr.length;
for (let i = 0; i < k; i++) {
const seq: number[] = [];
for (let j = i; j < n; j += k) seq.push(arr[j]);
const dp: number[] = [];
for (const x of seq) {
let l = 0, r = dp.length;
while (l < r) {
const m = (l + r) >> 1;
if (dp[m] > x) r = m; else l = m + 1;
}
if (l === dp.length) dp.push(x); else dp[l] = x;
}
ans += seq.length - dp.length;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log(n/k))— For each group, we compute LNDS using binary search, and there are k groups. - 🧺 Space complexity:
O(n)— We use extra space for the groups and DP arrays.