Get started

Minimum Operations to Make the Array K-Increasing — Hard Problem & Solution

You are given a 0-indexed array arr of n positive integers and a positive integer k.

Problem statement

You are given a 0-indexed array arr of n positive integers and a positive integer k. The array is K-increasing if arr[i - k] <= arr[i] holds for every index i with k <= i <= n - 1.

For example, [4,1,5,2,6,2] is K-increasing for k = 2 (arr[0] <= arr[2] <= arr[4] and arr[1] <= arr[3] <= arr[5]), but not for k = 1.

In one operation you may pick an index i and change arr[i] to any positive integer. Return the minimum number of operations needed to make the array K-increasing.

Example 1

Input: arr = [3,6,2,5,1,4], k = 2
Output: 4
Explanation: The chains `[3,2,1]` and `[6,5,4]` each keep only one element, so two changes per chain.

Example 2

Input: arr = [3,6,2,5,1,4], k = 3
Output: 1
Explanation: The chains are `[3,5]`, `[6,1]` and `[2,4]`; only `[6,1]` needs a change.

Example 3

Input: arr = [2,2,2,1], k = 1
Output: 1
Explanation: Equal neighbours are allowed; change the final 1.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i], k <= arr.length

How to solve Minimum Operations to Make the Array K-Increasing

K-increasing means each of the k interleaved chains is non-decreasing, and the chains do not interact. In a chain, the elements you keep must form a non-decreasing subsequence, and any such subsequence can be kept — the rest are rewritten. So the answer is the sum over chains of (length − longest non-decreasing subsequence).

Approach

  1. For each start s from 0 to k - 1, walk the chain arr[s], arr[s + k], ….
  2. Maintain tails, where tails[L] is the smallest possible last value of a non-decreasing subsequence of length L + 1.
  3. For each value x, find the first position whose tail is greater than x (upper bound) and put x there, or append it if there is none.
  4. Add chain length − len(tails) to the answer.

Why it works

Changed values can be any positive integer, so between two kept values a <= b every rewritten element can be set to a (and elements before the first kept one to 1), which makes the whole chain non-decreasing. Conversely the untouched elements must already be non-decreasing. Minimising changes therefore means maximising the kept non-decreasing subsequence, and the patience method computes that length exactly — the upper bound lets equal values extend a run rather than replace it.

Complexity

  • Time — O(n log(n / k))
  • Space — O(n / k)

Pitfalls

  • Use the longest non-decreasing subsequence (upper bound), not strictly increasing (lower bound) — equal values are allowed.
  • The chains are independent; solving the whole array as one sequence is wrong for k > 1.
  • A quadratic LIS per chain is too slow when k = 1 and n = 10^5.

Reference solution

Python

from typing import List
from bisect import bisect_right

def kIncreasing(arr: List[int], k: int) -> int:
    ops = 0
    for s in range(k):
        tails = []
        length = 0
        for i in range(s, len(arr), k):
            x = arr[i]
            length += 1
            pos = bisect_right(tails, x)
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
        ops += length - len(tails)
    return ops

JavaScript

var kIncreasing = function(arr, k) {
    var ops = 0;
    for (var s = 0; s < k; s++) {
        var tails = [], length = 0;
        for (var i = s; i < arr.length; i += k) {
            var x = arr[i];
            length++;
            var lo = 0, hi = tails.length;
            while (lo < hi) {
                var mid = (lo + hi) >> 1;
                if (tails[mid] <= x) lo = mid + 1; else hi = mid;
            }
            if (lo === tails.length) tails.push(x); else tails[lo] = x;
        }
        ops += length - tails.length;
    }
    return ops;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming