Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 629 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 629 # by problem number
lcpy gen -s k_inverse_pairs_array # by problem name
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 consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7.
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.
Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
class Solution:
# Time: O(n * k)
# Space: O(k)
def k_inverse_pairs(self, n: int, k: int) -> int:
mod = 1_000_000_007
# dp[j]: arrays using values 1..i with exactly j inverse pairs.
dp = [0] * (k + 1)
dp[0] = 1
for i in range(2, n + 1):
prefix = [0] * (k + 2)
for j in range(k + 1):
prefix[j + 1] = (prefix[j] + dp[j]) % mod
# Inserting value i adds between 0 and i-1 new inverse pairs.
new = [0] * (k + 1)
for j in range(k + 1):
low = max(0, j - (i - 1))
new[j] = (prefix[j + 1] - prefix[low]) % mod
dp = new
return dp[k]
| Time | Space |
|---|---|
| O(n * k) | O(k) |