Skip to content

2111. Minimum Operations to Make the Array K-Increasing

Description

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

 

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 <= 105
  • 1 <= arr[i], k <= arr.length

Solutions

Solution 1

Thinking

\(k\)-increasing only constrains subsequences whose indices share the same residue modulo \(k\). The \(k\) groups are independent, and the answer is the sum of their operation counts. In one group, an operation may rewrite any value, so the minimum edits equal the length minus the longest non-decreasing subsequence.

With \(n\le 10^5\), a quadratic LIS on each group is too slow. Ties are allowed, so \(\texttt{bisect\_right}\) on a patience array computes the longest non-decreasing length in \(O(L\log L)\).

We therefore process \(\textit{arr}[i::k]\) for each \(i<k\) and sum “group length minus LIS length”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        def lis(arr):
            t = []
            for x in arr:
                idx = bisect_right(t, x)
                if idx == len(t):
                    t.append(x)
                else:
                    t[idx] = x
            return len(arr) - len(t)

        return sum(lis(arr[i::k]) for i in range(k))

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int kIncreasing(int[] arr, int k) {
        int n = arr.length;
        int ans = 0;
        for (int i = 0; i < k; ++i) {
            List<Integer> t = new ArrayList<>();
            for (int j = i; j < n; j += k) {
                t.add(arr[j]);
            }
            ans += lis(t);
        }
        return ans;
    }

    private int lis(List<Integer> arr) {
        List<Integer> t = new ArrayList<>();
        for (int x : arr) {
            int idx = searchRight(t, x);
            if (idx == t.size()) {
                t.add(x);
            } else {
                t.set(idx, x);
            }
        }
        return arr.size() - t.size();
    }

    private int searchRight(List<Integer> arr, int x) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr.get(mid) > x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int kIncreasing(vector<int>& arr, int k) {
        int ans = 0, n = arr.size();
        for (int i = 0; i < k; ++i) {
            vector<int> t;
            for (int j = i; j < n; j += k) t.push_back(arr[j]);
            ans += lis(t);
        }
        return ans;
    }

    int lis(vector<int>& arr) {
        vector<int> t;
        for (int x : arr) {
            auto it = upper_bound(t.begin(), t.end(), x);
            if (it == t.end())
                t.push_back(x);
            else
                *it = x;
        }
        return arr.size() - t.size();
    }
};

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
func kIncreasing(arr []int, k int) int {
    searchRight := func(arr []int, x int) int {
        left, right := 0, len(arr)
        for left < right {
            mid := (left + right) >> 1
            if arr[mid] > x {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    lis := func(arr []int) int {
        var t []int
        for _, x := range arr {
            idx := searchRight(t, x)
            if idx == len(t) {
                t = append(t, x)
            } else {
                t[idx] = x
            }
        }
        return len(arr) - len(t)
    }

    n := len(arr)
    ans := 0
    for i := 0; i < k; i++ {
        var t []int
        for j := i; j < n; j += k {
            t = append(t, arr[j])
        }
        ans += lis(t)
    }
    return ans
}

Comments