Welcome to Subscribe On Youtube

629. K Inverse Pairs Array

Description

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

 

Constraints:

• 1 <= n <= 1000
• 0 <= k <= 1000

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int kInversePairs(int n, int k) {
          final int mod = (int) 1e9 + 7;
          int[] f = new int[k + 1];
          int[] s = new int[k + 2];
          f[0] = 1;
          Arrays.fill(s, 1);
          s[0] = 0;
          for (int i = 1; i <= n; ++i) {
              for (int j = 1; j <= k; ++j) {
                  f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
              }
              for (int j = 1; j <= k + 1; ++j) {
                  s[j] = (s[j - 1] + f[j - 1]) % mod;
              }
          }
          return f[k];
      }
  }
  

• class Solution {
  public:
      int kInversePairs(int n, int k) {
          int f[k + 1];
          int s[k + 2];
          memset(f, 0, sizeof(f));
          f[0] = 1;
          fill(s, s + k + 2, 1);
          s[0] = 0;
          const int mod = 1e9 + 7;
          for (int i = 1; i <= n; ++i) {
              for (int j = 1; j <= k; ++j) {
                  f[j] = (s[j + 1] - s[max(0, j - (i - 1))] + mod) % mod;
              }
              for (int j = 1; j <= k + 1; ++j) {
                  s[j] = (s[j - 1] + f[j - 1]) % mod;
              }
          }
          return f[k];
      }
  };
  

• class Solution:
      def kInversePairs(self, n: int, k: int) -> int:
          mod = 10**9 + 7
          f = [1] + [0] * k
          s = [0] * (k + 2)
          for i in range(1, n + 1):
              for j in range(1, k + 1):
                  f[j] = (s[j + 1] - s[max(0, j - (i - 1))]) % mod
              for j in range(1, k + 2):
                  s[j] = (s[j - 1] + f[j - 1]) % mod
          return f[k]
  
  

• func kInversePairs(n int, k int) int {
  	f := make([]int, k+1)
  	s := make([]int, k+2)
  	f[0] = 1
  	for i, x := range f {
  		s[i+1] = s[i] + x
  	}
  	const mod = 1e9 + 7
  	for i := 1; i <= n; i++ {
  		for j := 1; j <= k; j++ {
  			f[j] = (s[j+1] - s[max(0, j-(i-1))] + mod) % mod
  		}
  		for j := 1; j <= k+1; j++ {
  			s[j] = (s[j-1] + f[j-1]) % mod
  		}
  	}
  	return f[k]
  }
  

• function kInversePairs(n: number, k: number): number {
      const f: number[] = new Array(k + 1).fill(0);
      f[0] = 1;
      const s: number[] = new Array(k + 2).fill(1);
      s[0] = 0;
      const mod: number = 1e9 + 7;
      for (let i = 1; i <= n; ++i) {
          for (let j = 1; j <= k; ++j) {
              f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
          }
          for (let j = 1; j <= k + 1; ++j) {
              s[j] = (s[j - 1] + f[j - 1]) % mod;
          }
      }
      return f[k];
  }
  
  

All Problems

All Solutions