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 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 _theminimum number of operations required to make the array K-increasing for the given _k.

Examples

Example 1

1
2
3
4
5
6
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

1
2
3
4
5
6
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

1
2
3
4
5
6
7
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^5
  • 1 <= 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

  1. For each group (from 0 to k-1), collect elements at indices i, i+k, i+2k, …
  2. For each group, compute the length of the longest non-decreasing subsequence (LNDS) using binary search.
  3. The number of changes for the group is its size minus LNDS length.
  4. Sum changes for all groups to get the answer.
  5. Edge case: If the array is already k-increasing, answer is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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.