Scale Engineer

Minimum Operations to Make the Array K-Increasing

Hard
#1923Time: 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)`.
Algorithms
Binary Search
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

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

Trade-offs

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).

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem