LeetCode 2111 - Minimum Operations to Make the Array K-Increasing

LeetCode Problem 2111

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to transform a given array arr into a K-increasing array using the minimum number of operations. A K-increasing array is defined such that for every index i where i >= k, the condition arr[i-k] <= arr[i] holds. Each operation allows us to pick any index i and change arr[i] to any positive integer. The goal is to minimize the number of such operations.

In simpler terms, the array can be viewed as k independent subsequences formed by elements at indices i, i+k, i+2k, .... Each subsequence must be non-decreasing to satisfy the K-increasing condition. Hence, the problem reduces to computing how many elements in each subsequence must be modified to make that subsequence non-decreasing, and summing these counts across all k subsequences.

The input array can be very large (n up to 10^5), which means any naive O(n²) solution will be too slow. Each array element is a positive integer, and k is at least 1 but at most n.

Important edge cases include arrays that are already K-increasing (requiring 0 operations), arrays with a single element (always valid), and k values equal to 1 or n, which reduce the problem to familiar forms: making the array non-decreasing or checking a single subsequence.

Approaches

Brute Force

A brute-force solution would attempt to check every possible sequence of operations to enforce arr[i-k] <= arr[i]. For each index i >= k, if arr[i] < arr[i-k], we could change arr[i] to arr[i-k]. While this seems simple, it fails to consider that changing arr[i] may propagate problems forward, and enumerating all possibilities would result in exponential time complexity.

This approach is correct in principle but infeasible for large arrays due to combinatorial explosion.

Optimal Approach

The key insight is to notice that the problem can be decomposed into k independent subsequences: [arr[i], arr[i+k], arr[i+2k], ...] for i = 0..k-1. For each subsequence, the minimum number of changes required to make it non-decreasing is equal to the subsequence length minus the length of its Longest Non-Decreasing Subsequence (LNDS). This is a variant of the classic Longest Increasing Subsequence problem, adapted to allow equal elements. Using a binary search approach, LNDS can be found in O(m log m) time for a subsequence of length m.

After computing the number of changes required for all k subsequences, summing them gives the final answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Check all possible operations; infeasible
Optimal	O(n log n)	O(n)	Decompose into k subsequences and use LNDS with binary search

Algorithm Walkthrough

1. Initialize a variable res to 0, which will accumulate the total number of required operations.
2. For each i from 0 to k-1, construct a subsequence sub containing elements arr[i], arr[i+k], arr[i+2k], ....
3. For this subsequence sub, compute the length of its Longest Non-Decreasing Subsequence (LNDS) using a binary search method:

• Initialize an empty list ln representing the current LNDS.
• Iterate through each element num in sub. Use binary search to find the first index in ln where num is less than the value at that index. Replace that element if found, else append num to ln.

4. The number of operations required for this subsequence is len(sub) - len(ln).
5. Add this number to res.
6. Return res as the minimum number of operations to make arr K-increasing.

Why it works: By decomposing the array into k independent subsequences, we ensure the K-increasing property holds across all indices. Computing LNDS for each subsequence guarantees that the minimum number of elements are modified to achieve non-decreasing order, which directly translates to minimizing operations.

Python Solution

from typing import List
import bisect

class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        res = 0
        for i in range(k):
            sub = arr[i::k]
            ln = []
            for num in sub:
                idx = bisect.bisect_right(ln, num)
                if idx == len(ln):
                    ln.append(num)
                else:
                    ln[idx] = num
            res += len(sub) - len(ln)
        return res

Implementation walkthrough: For each subsequence extracted with arr[i::k], we maintain a list ln representing the current Longest Non-Decreasing Subsequence. bisect_right ensures we allow equal elements, as the problem allows non-decreasing order. The difference between subsequence length and LNDS length gives the minimal number of changes needed.

Go Solution

import "sort"

func kIncreasing(arr []int, k int) int {
    res := 0
    for i := 0; i < k; i++ {
        var sub []int
        for j := i; j < len(arr); j += k {
            sub = append(sub, arr[j])
        }
        ln := []int{}
        for _, num := range sub {
            idx := sort.Search(len(ln), func(j int) bool { return ln[j] > num })
            if idx == len(ln) {
                ln = append(ln, num)
            } else {
                ln[idx] = num
            }
        }
        res += len(sub) - len(ln)
    }
    return res
}

Go-specific notes: Go does not have a built-in bisect_right, so sort.Search is used to find the insertion index for the first element greater than num. Slice operations efficiently maintain the LNDS. Integer overflow is not an issue because elements are positive integers within constraints.

Worked Examples

Example 1: arr = [5,4,3,2,1], k = 1

Subsequences: [5,4,3,2,1]

LNDS of [5,4,3,2,1] is [5] (length 1)

Operations: 5 - 1 = 4

Answer: 4

Example 2: arr = [4,1,5,2,6,2], k = 2

Subsequence 0: [4,5,6], LNDS = [4,5,6] → 0 changes

Subsequence 1: [1,2,2], LNDS = [1,2,2] → 0 changes

Total operations = 0

Answer: 0

Example 3: arr = [4,1,5,2,6,2], k = 3

Subsequence 0: [4,2], LNDS = [2] → 1 change

Subsequence 1: [1,6], LNDS = [1,6] → 0 changes

Subsequence 2: [5,2], LNDS = [2] → 1 change

Total operations = 1 + 0 + 1 = 2

Answer: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each of the k subsequences has at most n/k elements. Finding LNDS for each takes O((n/k) log(n/k)), summing over k gives O(n log n)
Space	O(n)	Storing the subsequences and LNDS lists

The binary search approach ensures that we do not exceed O(n log n) even for large arrays.

Test Cases

# Provided examples
assert Solution().kIncreasing([5,4,3,2,1], 1) == 4  # decreasing array
assert Solution().kIncreasing([4,1,5,2,6,2], 2) == 0  # already K-increasing
assert Solution().kIncreasing([4,1,5,2,6,2], 3) == 2  # requires 2 changes

# Edge cases
assert Solution().kIncreasing([1], 1) == 0  # single element
assert Solution().kIncreasing([1,2,3,4,5], 5) == 0  # k = n, all subsequences length 1
assert Solution().kIncreasing([5,4,3,2,1], 2) == 2  # multiple subsequences
assert Solution().kIncreasing([1,2,1,2,1,2], 2) == 0  # alternating sequence, already K-increasing
assert Solution().kIncreasing([3,1,2,1,2,1], 2) == 2  # minimal changes needed

Test	Why
[5,4,3,2,1], k=1	Array fully decreasing; tests