Skip to main content
Talentd

Minimum Operations to Make the Array K-Increasing - Solution & Explanation

HardArrayBinary Search12 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

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

Approach 1: Divide and Solve Subproblems Using LIS

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:

  1. Divide the array into k-length subsequences.
  2. For each subsequence, find the LIS. The number of changes required for each subsequence is the size of the sequence minus the length of its LIS.
  3. Sum up the changes required for all subsequences.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(n), due to the DP array used for finding the LIS.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DP Longest Non-Decreasing Subsequence per subsequenceO(n²)O(n)Good for understanding the subsequence transformation or when constraints are small
Divide into K groups + LIS with Binary SearchO(n log n)O(n)Optimal solution for large inputs; typical interview expectation

Video Solution

Minimum Operations to Make the Array K-Increasing | Leetcode 2111 | Live coding session | LIS 🔥🔥🔥 • Coding Decoded • 2,029 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make the Array K-Increasing easy or hard?
Minimum Operations to Make the Array K-Increasing is categorized as a Hard problem. The difficulty comes from recognizing that the constraint splits the array into k independent chains and that minimizing modifications reduces to computing the longest non-decreasing subsequence efficiently.
Minimum Operations to Make the Array K-Increasing Python/Java solution
Implement the solution by iterating through each starting index from 0 to k-1, building the subsequence arr[i], arr[i+k], arr[i+2k], and computing its longest non-decreasing subsequence using binary search. The same logic works in Python, Java, C++, JavaScript, and C# using built-in binary search utilities or manual implementations.
How to solve Minimum Operations to Make the Array K-Increasing in O(n log n)?
Group elements by index modulo k so that each subsequence contains indices i, i+k, i+2k. For each subsequence, compute the longest non-decreasing subsequence using the patience sorting technique with binary search (upper bound). The minimum operations equal the subsequence length minus the LNDS length.
What is the best approach for Minimum Operations to Make the Array K-Increasing?
The optimal approach splits the array into k independent subsequences using indices i, i+k, i+2k. Each subsequence must be non-decreasing. Compute the longest non-decreasing subsequence (LNDS) for each group using a binary-search-based LIS technique and sum m - LNDS for each subsequence. This runs in O(n log n) time.
Is Minimum Operations to Make the Array K-Increasing asked at Google/Amazon/Meta?
Variants of subsequence optimization and LIS-based problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests recognition of LIS patterns combined with array partitioning by index spacing.
What data structure is used in Minimum Operations to Make the Array K-Increasing?
The optimized solution uses arrays (or lists) to store subsequences and a dynamic tails array for the LIS computation. Binary search is applied on the tails array to maintain the smallest possible ending values for subsequences of different lengths.
What is the time complexity of Minimum Operations to Make the Array K-Increasing?
The optimal solution runs in O(n log n) time. Each of the k subsequences is processed using a longest non-decreasing subsequence algorithm implemented with binary search, which takes O(m log m) for subsequence length m. Total space complexity is O(n).

Ready to solve this problem?

Practice Minimum Operations to Make the Array K-Increasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Increasing Subsequence

Next

Minimum Swaps To Make Sequences Increasing