Minimum Operations to Make the Array K-Increasing

medium dp binary search

Problem

Given arr and an integer k, the array is k-increasing if arr[i − k] ≤ arr[i] for every valid i. In one operation you may set any element to any value. Return the minimum number of operations to make arr k-increasing.

Inputarr = [5,4,3,2,1], k = 1

Output4

The whole array must become non-decreasing; only one element can stay.

arr

from bisect import bisect_right

def kIncreasing(arr, k):
    n = len(arr)
    ops = 0
    for r in range(k):
        chain = arr[r:n:k]
        tails = []
        for x in chain:
            i = bisect_right(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        ops += len(chain) - len(tails)
    return ops

function kIncreasing(arr, k) {
  const n = arr.length;
  let ops = 0;
  for (let r = 0; r < k; r++) {
    const tails = [];
    let len = 0;
    for (let i = r; i < n; i += k) {
      const pos = upperBound(tails, arr[i]);
      if (pos === tails.length) tails.push(arr[i]);
      else tails[pos] = arr[i];
      len++;
    }
    ops += len - tails.length;
  }
  return ops;
}
function upperBound(a, x) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] <= x) lo = mid + 1; else hi = mid;
  }
  return lo;
}

class Solution {
    public int kIncreasing(int[] arr, int k) {
        int n = arr.length, ops = 0;
        for (int r = 0; r < k; r++) {
            List<Integer> tails = new ArrayList<>();
            int len = 0;
            for (int i = r; i < n; i += k) {
                int pos = upperBound(tails, arr[i]);
                if (pos == tails.size()) tails.add(arr[i]);
                else tails.set(pos, arr[i]);
                len++;
            }
            ops += len - tails.size();
        }
        return ops;
    }
    private int upperBound(List<Integer> a, int x) {
        int lo = 0, hi = a.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a.get(mid) <= x) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

int kIncreasing(vector<int>& arr, int k) {
    int n = arr.size(), ops = 0;
    for (int r = 0; r < k; r++) {
        vector<int> tails;
        int len = 0;
        for (int i = r; i < n; i += k) {
            auto it = upper_bound(tails.begin(), tails.end(), arr[i]);
            if (it == tails.end()) tails.push_back(arr[i]);
            else *it = arr[i];
            len++;
        }
        ops += len - (int)tails.size();
    }
    return ops;
}

Explanation

The condition arr[i−k] ≤ arr[i] only ever compares elements whose indices differ by a multiple of k. So the array splits into k independent chains: indices r, r+k, r+2k, … for each remainder r. Each chain must end up non-decreasing on its own.

For one chain, the cheapest way to make it non-decreasing is to keep as many elements as possible and overwrite the rest. The elements we keep must already form a non-decreasing subsequence, so we want the longest non-decreasing subsequence (LNDS); everything outside it is one operation each.

We compute the LNDS length with the classic patience / tails trick: maintain a tails array where tails[i] is the smallest possible ending value of a non-decreasing subsequence of length i+1. For each value we binary-search the first tail strictly greater than it (upper_bound, which allows equal values to extend) and replace it, or append if none is larger.

The number of operations for a chain is chainLength − LNDS. Summing this across all k chains gives the total minimum operations.

Example: arr = [5,4,3,2,1], k = 1 is one chain. Its longest non-decreasing subsequence has length 1, so we change 5 − 1 = 4 elements. The answer is 4.

Time: O(n log n) Space: O(n)