Minimum Operations to Make the Array K-Increasing

Minimum Operations to Make the Array K-Increasing - Problem

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.

Input & Output

Example 1 — Basic K-increasing

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

› Output: 1

💡 Note: Split into subsequences: [4,5,6] (already increasing) and [1,2,2] (need to change one element to make it strictly increasing). Total operations = 1.

Example 2 — All elements need changes

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

› Output: 4

💡 Note: For k=1, entire array must be non-decreasing. We need to change 4 elements to make [5,4,3,2,1] into something like [1,2,3,4,5].

Example 3 — Already K-increasing

$ Input: arr = [1,2,3,4], k = 2

› Output: 0

💡 Note: Subsequence [1,3] and [2,4] are both already increasing, so no operations needed.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
1 ≤ k ≤ arr.length

Visualization

Tap to expand

Understanding the Visualization

Input Array

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

Split into Subsequences

Group by index % k: [4,5,6] and [1,2,2]

Find Operations

LIS approach: 0 + 1 = 1 operation needed

Key Takeaway

🎯 Key Insight: Transform K-increasing problem into k independent LIS problems for optimal solution

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to split the array into k independent subsequences where elements at positions i, i+k, i+2k, ... form each subsequence. For each subsequence, find the longest increasing subsequence (LIS) and change all other elements. Best approach uses binary search to find LIS efficiently. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimized LIS	O(n log n)	O(n)	Use binary search to find LIS in O(n log n) time
Longest Increasing Subsequence (LIS) Approach	O(n²)	O(n)	Find LIS in each subsequence and change the rest
Brute Force with Recursion	O(2^n)	O(n)	Try all possible modifications and choose the minimum operations

Binary Search Optimized LIS — Algorithm Steps

Step 1: Split array into k subsequences
Step 2: For each subsequence, find LIS using binary search approach
Step 3: Use patience sorting concept with binary search

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize tails array

Track smallest tail of increasing subsequence of each length

Binary search position

For each element, find where to place/replace in tails

Update and count

LIS length = tails array length

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binarySearch(int* arr, int len, int target) {
    int left = 0, right = len;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int solution(int* arr, int n, int k) {
    int totalOperations = 0;
    
    // Process each subsequence
    for (int start = 0; start < k; start++) {
        int subsequence[1000];
        int m = 0;
        
        // Extract subsequence starting at index 'start' with step k
        for (int i = start; i < n; i += k) {
            subsequence[m++] = arr[i];
        }
        
        if (m <= 1) {
            continue;
        }
        
        // Find LIS length using binary search approach
        int tails[1000];
        int tailsLen = 0;
        
        for (int j = 0; j < m; j++) {
            int num = subsequence[j];
            // Find position to insert/replace using binary search
            int pos = binarySearch(tails, tailsLen, num);
            if (pos == tailsLen) {
                tails[tailsLen++] = num;
            } else {
                tails[pos] = num;
            }
        }
        
        int lisLength = tailsLen;
        int operationsNeeded = m - lisLength;
        totalOperations += operationsNeeded;
    }
    
    return totalOperations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[],");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(arr, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

For each element, binary search takes O(log n), total O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Store k subsequences and tails array for binary search LIS

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimized LIS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler