Minimum Operations to Make the Array K-Increasing

Hard
1519.

Minimum Operations to Make the Array K-Increasing

Minimum Operations to Make the Array K-Increasing is a hard coding problem on arrays, dynamic programming and binary search, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var kIncreasing = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make the Array K-Increasing — Solution

Minimum Operations to Make the Array K-Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make the Array K-Increasing is a hard coding problem on arrays, dynamic programming and binary search, asked in Amazon and Google interviews.

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

Hints for Minimum Operations to Make the Array K-Increasing

  1. Hint 1

    The condition only ever compares indices that are k apart. Split the array into k independent chains: indices s, s + k, s + 2k, … for each s < k.

  2. Hint 2

    Within one chain, the elements you leave untouched must already be non-decreasing; every other element can be rewritten to fit between its kept neighbours.

  3. Hint 3

    So each chain costs its length minus its longest non-decreasing subsequence. Compute that in O(m log m) with the patience method, using an upper-bound search so equal values extend the sequence.

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

Java

public static int kIncreasing(int[] arr, int k) {
    int n = arr.length, ops = 0;
    int[] tails = new int[n];
    for (int s = 0; s < k; s++) {
        int size = 0, length = 0;
        for (int i = s; i < n; i += k) {
            int x = arr[i];
            length++;
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] <= x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        ops += length - size;
    }
    return ops;
}

C++

int kIncreasing(vector<int>& arr, int k) {
    int n = arr.size(), ops = 0;
    for (int s = 0; s < k; s++) {
        vector<int> tails;
        int length = 0;
        for (int i = s; i < n; i += k) {
            length++;
            auto it = upper_bound(tails.begin(), tails.end(), arr[i]);
            if (it == tails.end()) tails.push_back(arr[i]);
            else *it = arr[i];
        }
        ops += length - (int)tails.size();
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming