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.
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)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 <= 1051 <= arr[i], k <= arr.lengthProblem Overview: You receive an integer array arr and an integer k. The array is k-increasing if every element satisfies arr[i] >= arr[i-k] for all valid i. You can change any value in the array. The task is to compute the minimum number of operations required to make the array satisfy this constraint.
Approach 1: Longest Non-Decreasing Subsequence per Group (DP) (Time: O(n²), Space: O(n))
Elements that interact with each other are spaced exactly k apart. This means the array naturally splits into k independent subsequences: indices i, i+k, i+2k.... Each subsequence must be non-decreasing. For a subsequence of length m, the minimum operations equal m - LNDS (longest non-decreasing subsequence). A straightforward dynamic programming solution computes LNDS by checking all previous elements and extending valid subsequences. This takes O(m²) time per group and O(n²) overall in the worst case. The idea is conceptually simple and useful for understanding the transformation into subsequence problems.
Approach 2: Divide into K Subsequences + LIS with Binary Search (Time: O(n log n), Space: O(n))
A faster solution uses the same decomposition into k independent subsequences but computes the longest non-decreasing subsequence using the classic patience sorting technique with binary search. For each subsequence, maintain a tails array where tails[x] stores the smallest ending value of a non-decreasing subsequence of length x+1. Iterate through the subsequence and place each value using an upper_bound-style binary search so equal values are allowed (non-decreasing condition). This reduces the LNDS computation to O(m log m) for a subsequence of length m. Summed across all groups, the complexity becomes O(n log(n/k)), which is effectively O(n log n).
This approach relies on two observations: the k-gap constraint isolates dependencies into separate chains, and minimizing modifications is equivalent to keeping the longest valid subsequence. The remaining elements in each chain must be modified. Using binary search dramatically speeds up subsequence computation compared to quadratic DP.
Key concepts involved include array partitioning with modular indexing, subsequence optimization, and efficient searching using binary search on top of an array-based structure.
Recommended for interviews: The LIS + binary search solution is what interviewers expect. Recognizing that the constraint splits the problem into k independent sequences shows strong problem decomposition skills. Explaining the quadratic LNDS approach first demonstrates understanding, while implementing the O(n log n) optimization shows mastery of subsequence techniques.
The first approach is to divide the original array into k-length subsequences and solve each of these subsequences independently. By focusing on making each subsequence non-decreasing, we can apply the concept of the Longest Increasing Subsequence (LIS). The transformation of each subsequence into the LIS will give insight into the minimum operations required.
Steps:
This C solution divides the array into subsequences based on k and calculates the minimum operations needed to make each subsequence an increasing subsequence using a technique to find the Longest Increasing Subsequence.
Time Complexity: O(n log n/k), since for each subsequence (of size n/k) we find the LIS, which takes O(n log n/k).
Space Complexity: O(n), due to the DP array used for finding the LIS.
| Approach | Complexity |
|---|---|
| Divide and Solve Subproblems Using LIS | Time Complexity: O(n log n/k), since for each subsequence (of size n/k) we find the LIS, which takes O(n log n/k). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP Longest Non-Decreasing Subsequence per subsequence | O(n²) | O(n) | Good for understanding the subsequence transformation or when constraints are small |
| Divide into K groups + LIS with Binary Search | O(n log n) | O(n) | Optimal solution for large inputs; typical interview expectation |
Minimum Operations to Make the Array K-Increasing | Leetcode 2111 | Live coding session | LIS 🔥🔥🔥 • Coding Decoded • 2,000 views views
Watch 8 more video solutions →Practice Minimum Operations to Make the Array K-Increasing with our built-in code editor and test cases.
Practice on FleetCode