Minimum operations to make the array k increasing

Array Binary Search

40.2% acceptance

Feb 25, 2026

727

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn k_increasing(arr: Vec<i32>, k: i32) -> i32 {
    let n = arr.len();
    let k = k as usize;
    let mut ops = 0usize;

    // For each group starting at index `start`, find LIS (non-decreasing)
    // ops for that group = group_len - LIS_length
    for start in 0..k {
      let seq: Vec<i32> = (0..)
        .map(|i| start + i * k)
        .take_while(|&j| j < n)
        .map(|j| arr[j])
        .collect();
      let lis_len = Self::lis_non_decreasing(&seq);
      ops += seq.len() - lis_len;
    }
    ops as i32
  }

  fn lis_non_decreasing(seq: &[i32]) -> usize {
    // Patience sorting for non-decreasing LIS (allows equal elements)
    let mut tails: Vec<i32> = Vec::new();
    for &x in seq {
      // find first tail strictly greater than x
      let pos = tails.partition_point(|&t| t <= x);
      if pos == tails.len() {
        tails.push(x);
      } else {
        tails[pos] = x;
      }
    }
    tails.len()
  }
}