{x}
blog image

Minimum Operations to Make the Array K-Increasing

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

Solution Explanation

This problem asks for the minimum number of operations to make the array K-increasing. An array is K-increasing if arr[i-k] <= arr[i] for every index i where k <= i <= n-1. The solution leverages the concept of Longest Increasing Subsequence (LIS) to efficiently solve this problem.

Core Idea:

The problem can be broken down into k subproblems. For each subproblem, we consider a subsequence of the input array arr formed by taking elements at indices i, i+k, i+2k, ... This subsequence needs to be non-decreasing (a special case of K-increasing where k=1). Finding the minimum number of operations to make this subsequence non-decreasing is equivalent to finding the length of the LIS of this subsequence. The difference between the subsequence length and the length of its LIS represents the number of operations needed.

Algorithm:

  1. Iteration: Iterate k times (from i = 0 to k-1). In each iteration, extract a subsequence from arr where elements are spaced k apart, starting at index i.

  2. Longest Increasing Subsequence (LIS): For each subsequence, find the LIS. There are several ways to compute the LIS; a common and efficient approach is using binary search. This involves maintaining a sorted array t to store the tails of increasing subsequences. Each element x in the subsequence is compared against t; if x is greater than all elements in t, it extends the LIS, otherwise it replaces the smallest element in t that is greater than or equal to x (using binary search to efficiently find this element).

  3. Operation Count: The difference between the length of the subsequence and the length of its LIS (which is the length of the t array) gives the number of elements that need to be changed to make the subsequence non-decreasing. This counts the minimum operations for that subsequence.

  4. Total Operations: Sum the operation counts from all k subsequences to get the final answer.

Time Complexity: The outer loop iterates k times. For each iteration, the LIS computation using binary search takes O(n/k * log(n/k)) time, where n is the length of arr. Thus, the overall time complexity is O(k * (n/k) * log(n/k)) = O(n * log(n/k)). In the worst case (k=1), this becomes O(n log n).

Space Complexity: The space complexity is determined by the space needed to store the t array in each LIS computation. In the worst case, this is O(n/k). The overall space complexity is O(n) in the worst-case scenario.

Code Explanation (Python):

import bisect
 
class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        def lis(arr):  # Function to calculate LIS using binary search
            t = []
            for x in arr:
                idx = bisect_right(t, x) #Finds index to insert x maintaining sorted order
                if idx == len(t):
                    t.append(x)
                else:
                    t[idx] = x
            return len(arr) - len(t) #Difference is number of operations needed
 
        return sum(lis(arr[i::k]) for i in range(k)) #Iterates and sums up operations for each subsequence

The other languages (Java, C++, Go) implement the same algorithm, with variations in syntax and data structures, but maintain the same time and space complexity. The lis function in each language uses binary search to compute the LIS efficiently.