# Minimum Operations to Make the Array K-Increasing
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-the-array-k-increasing
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## 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 _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`

# Approaches
## Decomposition with Naive DP for LNDS
The problem can be broken down into `k` independent subproblems. The condition `arr[i-k] <= arr[i]` only relates elements that are `k` indices apart. This means we can partition the array into `k` subsequences: `(arr[0], arr[k], ...), (arr[1], arr[1+k], ...), ..., (arr[k-1], arr[k-1+k], ...)`. For the whole array to be K-increasing, each of these subsequences must be non-decreasing. The minimum operations to make a sequence non-decreasing is its length minus the length of its Longest Non-decreasing Subsequence (LNDS). This approach calculates the LNDS for each subsequence using a standard dynamic programming algorithm with quadratic time complexity.
**Time:** O(n^2 / k). The outer loop runs `k` times. Inside the loop, we construct a subsequence of size `m ≈ n/k`. The `lengthOfLNDS` function takes O(m^2) time. Therefore, the total time complexity is `k * O((n/k)^2) = O(k * n^2 / k^2) = O(n^2 / k)`. The worst-case is when `k=1`, leading to `O(n^2)`. · **Space:** O(n/k). For each of the `k` iterations, we create a subsequence of size roughly `n/k` and a `dp` array of the same size. Since this space is reused in each iteration, the peak space complexity is determined by the largest subsequence, which is `O(n/k)`.
**Pros:** Conceptually straightforward and easy to implement.; Correctly identifies the problem structure of independent subsequences.
**Cons:** The quadratic time complexity for finding the LNDS makes this approach inefficient for large subsequences.; It will likely result in a 'Time Limit Exceeded' error for test cases with a small `k` and large `n` (e.g., `k=1`, `n=10^5`).
### Explanation
The core idea is to recognize the independence of the `k` subsequences. We can solve the problem for each subsequence and sum the results. We iterate from `i = 0` to `k-1` to handle each starting point.

For each starting index `i`, we create a temporary list containing elements `arr[i], arr[i+k], arr[i+2k], ...`. On this temporary list, we apply a classic dynamic programming algorithm to find the length of the LNDS. Let the subsequence be `sub`. We define `dp[j]` as the length of the LNDS of `sub` ending at index `j`. The recurrence relation is `dp[j] = 1 + max({dp[l] | 0 <= l < j and sub[l] <= sub[j]})`. The length of the LNDS for `sub` is the maximum value in the `dp` array. The number of changes needed for this subsequence is `sub.size() - lnds_length`. We sum up the changes for all `k` subsequences to get the total minimum operations.

```java
class Solution {
    public int kIncreasing(int[] arr, int k) {
        int totalOperations = 0;
        int n = arr.length;

        for (int i = 0; i < k; i++) {
            List<Integer> subsequence = new ArrayList<>();
            for (int j = i; j < n; j += k) {
                subsequence.add(arr[j]);
            }
            if (subsequence.size() > 0) {
                int lndsLength = lengthOfLNDS(subsequence);
                totalOperations += subsequence.size() - lndsLength;
            }
        }
        return totalOperations;
    }

    // O(m^2) DP approach for Longest Non-decreasing Subsequence
    private int lengthOfLNDS(List<Integer> sub) {
        int m = sub.size();
        if (m == 0) {
            return 0;
        }
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        int maxLength = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                if (sub.get(j) <= sub.get(i)) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }
}
```
### Algorithm
1.  Initialize a variable `totalOperations` to 0.
2.  Iterate from `i = 0` to `k-1`. In each iteration, we process one of the `k` independent subsequences.
3.  For each `i`, extract the subsequence `sub = [arr[i], arr[i+k], arr[i+2k], ...] ` into a temporary list.
4.  Calculate the length of the Longest Non-decreasing Subsequence (LNDS) for `sub` using a dynamic programming approach.
    - Let `m` be the length of `sub`.
    - Create a `dp` array of size `m`, where `dp[j]` will store the length of the LNDS ending at index `j` of `sub`.
    - Initialize all elements of `dp` to 1.
    - Iterate `j` from 1 to `m-1`:
        - Iterate `p` from 0 to `j-1`:
            - If `sub[p] <= sub[j]`, it means we can extend a non-decreasing subsequence ending at `p`. Update `dp[j] = max(dp[j], 1 + dp[p])`.
    - The length of the LNDS for `sub` is the maximum value in the `dp` array.
5.  The minimum operations required for the current subsequence is its length minus the LNDS length (`m - lndsLength`).
6.  Add this count to `totalOperations`.
7.  After the outer loop finishes, `totalOperations` holds the final answer.

## Decomposition with Optimized LNDS (Binary Search)
This approach also starts by decomposing the array into `k` independent subsequences. The key improvement is using a more efficient algorithm to find the length of the Longest Non-decreasing Subsequence (LNDS) for each subsequence. Instead of the `O(m^2)` DP approach, we use an `O(m log m)` algorithm based on patience sorting and binary search. This significantly improves the overall time complexity, making it efficient enough for the given constraints.
**Time:** O(n * log(n/k)). The outer loop runs `k` times. For each subsequence of size `m ≈ n/k`, the `lengthOfLNDS` function takes `O(m log m)` time due to the binary search. The total time is `k * O((n/k) * log(n/k)) = O(n * log(n/k))`. This is efficient enough for `n=10^5` regardless of the value of `k`. · **Space:** O(n/k). Similar to the previous approach, the space is dominated by storing one subsequence and its corresponding `tails` list. The largest subsequence has size `O(n/k)`, so the space complexity is `O(n/k)`.
**Pros:** Highly efficient and optimal time complexity for the given constraints.; Passes all test cases on platforms like LeetCode.
**Cons:** The binary search-based algorithm for LNDS is less intuitive than the standard DP approach.
### Explanation
Like the previous approach, we process `k` independent subsequences. The crucial optimization lies in how we find the length of the LNDS. For a subsequence of length `m`, we can find its LNDS length in `O(m log m)` time.

This is achieved by maintaining a sorted list, `tails`. This list does not store the LNDS itself, but rather the smallest possible tail for all non-decreasing subsequences of a given length. We iterate through each number `x` of the subsequence:
- If `tails` is empty or `x` is greater than or equal to the last element of `tails`, it means `x` can extend the longest non-decreasing subsequence found so far. We append `x` to `tails`.
- Otherwise, `x` can be the new end of a shorter non-decreasing subsequence. We find the first element in `tails` that is strictly greater than `x` and replace it. This is done using binary search. This step is key: it doesn't increase the length of `tails`, but it makes the tail of a subsequence smaller, which increases the chances of extending it later.

The final size of the `tails` list gives the length of the LNDS. The total operations is the sum of `subsequence.size() - lndsLength` over all `k` subsequences.

```java
class Solution {
    public int kIncreasing(int[] arr, int k) {
        int totalOperations = 0;
        int n = arr.length;

        for (int i = 0; i < k; i++) {
            List<Integer> subsequence = new ArrayList<>();
            for (int j = i; j < n; j += k) {
                subsequence.add(arr[j]);
            }
            if (subsequence.size() > 0) {
                int lndsLength = lengthOfLNDS(subsequence);
                totalOperations += subsequence.size() - lndsLength;
            }
        }
        return totalOperations;
    }

    // O(m log m) approach for Longest Non-decreasing Subsequence
    private int lengthOfLNDS(List<Integer> sub) {
        List<Integer> tails = new ArrayList<>();
        for (int num : sub) {
            if (tails.isEmpty() || num >= tails.get(tails.size() - 1)) {
                tails.add(num);
            } else {
                // Find the first element in tails > num (upper_bound)
                int left = 0, right = tails.size() - 1;
                int insertionPoint = tails.size();
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (tails.get(mid) > num) {
                        insertionPoint = mid;
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                tails.set(insertionPoint, num);
            }
        }
        return tails.size();
    }
}
```
### Algorithm
1.  Initialize `totalOperations` to 0.
2.  Loop `i` from `0` to `k-1` to process each of the `k` independent subsequences.
3.  For each `i`, create a list `subsequence` containing `arr[i], arr[i+k], ...`.
4.  Calculate the length of the Longest Non-decreasing Subsequence (LNDS) for `subsequence` using an efficient `O(m log m)` algorithm (where `m` is the subsequence length).
    - Create an empty list `tails`.
    - For each number `num` in `subsequence`:
        - If `tails` is empty or `num` is greater than or equal to the last element of `tails`, add `num` to the end of `tails`.
        - Otherwise, find the smallest element in `tails` that is strictly greater than `num`. This can be found using binary search. Replace that element with `num`.
    - The final size of the `tails` list is the length of the LNDS.
5.  The number of operations for the current subsequence is `subsequence.size() - tails.size()`.
6.  Add this number to `totalOperations`.
7.  Return `totalOperations` after the loop.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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();
  }
};

```

### Python

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

```