Count the number of inversions

Array Dynamic Programming

29.7% acceptance

Feb 24, 2026

183

You are given an integer n and a 2D array requirements, where requirements[i] = [endi, cnti] represents the end index and the inversion count of each requirement. A pair of indices (i, j) from an integer array nums is called an inversion if: i < j and nums[i] > nums[j] Return the number of permutations perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..endi] has exactly cnti inversions. Since the answer may be very large, return it modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_permutations(n: i32, requirements: Vec<Vec<i32>>) -> i32 {
    const MOD: u64 = 1_000_000_007;
    let n = n as usize;
    // req[i] = Some(cnt) if there's a requirement at index i
    let mut req = vec![None::<usize>; n];
    for r in &requirements {
      req[r[0] as usize] = Some(r[1] as usize);
    }
    // Requirement at index 0 must be 0 if it exists
    if let Some(cnt) = req[0] {
      if cnt != 0 {
        return 0;
      }
    }
    let max_inv = 400;
    // dp[j] = number of ways to arrange first i+1 elements with j inversions
    let mut dp = vec![0u64; max_inv + 1];
    dp[0] = 1;

    for i in 1..n {
      let mut ndp = vec![0u64; max_inv + 1];
      // prefix sums for sliding window
      let mut prefix = vec![0u64; max_inv + 2];
      for j in 0..=max_inv {
        prefix[j + 1] = (prefix[j] + dp[j]) % MOD;
      }
      for j in 0..=max_inv {
        // Can insert element i (0-indexed, value = i) at any of i+1 positions
        // inserting at k positions from right gives k new inversions (0<=k<=i)
        // ndp[j] = sum dp[j-k] for k in 0..=min(j, i) = sum dp[j-i..=j]
        let lo = if j >= i { j - i } else { 0 };
        let hi = j;
        ndp[j] = (prefix[hi + 1] - prefix[lo] + MOD) % MOD;
      }
      // Apply requirement if exists
      if let Some(cnt) = req[i] {
        let mut restricted = vec![0u64; max_inv + 1];
        if cnt <= max_inv {
          restricted[cnt] = ndp[cnt];
        }
        dp = restricted;
      } else {
        dp = ndp;
      }
    }

    let last_end = *requirements.iter().map(|r| &r[0]).max().unwrap() as usize;
    let last_cnt = req[last_end].unwrap();
    dp[last_cnt] as i32
  }
}