K inverse pairs array

Dynamic Programming

49.0% acceptance

Feb 20, 2026

2777

331

Return the number of arrays of length n with numbers 1..n that have exactly k inverse pairs, modulo 1e9+7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn k_inverse_pairs(n: i32, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let k = k as usize;
    // dp[j] = count of perms of 1..i with j inverse pairs
    let mut dp = vec![0i64; k + 1];
    dp[0] = 1;
    for i in 2..=n {
      // prefix sums for window slide
      let mut prefix = vec![0i64; k + 2];
      for j in 0..=k {
        prefix[j + 1] = (prefix[j] + dp[j]) % MOD;
      }
      for j in 0..=k {
        let hi = prefix[j + 1];
        let lo = if j >= i { prefix[j + 1 - i] } else { 0 };
        dp[j] = (hi - lo + MOD) % MOD;
      }
    }
    dp[k] as i32
  }
}