Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 consisting 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 <= 10000 <= k <= 1000Problem summary: 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 consisting 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
3 0
3 1
count-the-number-of-inversions)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #629: K Inverse Pairs Array
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];
}
}
// Accepted solution for LeetCode #629: K Inverse Pairs Array
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]
}
# Accepted solution for LeetCode #629: K Inverse Pairs Array
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]
// Accepted solution for LeetCode #629: K Inverse Pairs Array
/**
* [0629] K Inverse Pairs Array
*
* 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 10^9 + 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
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/k-inverse-pairs-array/
// discuss: https://leetcode.com/problems/k-inverse-pairs-array/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
const MOD: i32 = 1_000_000_007;
impl Solution {
pub fn k_inverse_pairs(n: i32, k: i32) -> i32 {
// There is at most n * (n - 1) / 2 pairs
if k > n * (n - 1) / 2 {
return 0;
}
// dp[k] represents the number of k different arrays consist of numbers
let mut dp = vec![0; k as usize + 1];
// Only one array meets this: [1, 2, 3, ..., n]
dp[0] = 1;
for i in 1..=n as usize {
let mut row = vec![0; k as usize + 1];
let mut sum = 0i32;
for j in 0..=k as usize {
sum += dp[j];
if j >= i {
sum -= dp[j - i];
}
sum = sum.rem_euclid(MOD);
row[j] = sum;
}
dp = row;
}
dp[k as usize]
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0629_example_1() {
let n = 3;
let k = 0;
let result = 1;
assert_eq!(Solution::k_inverse_pairs(n, k), result);
}
#[test]
fn test_0629_example_2() {
let n = 3;
let k = 1;
let result = 2;
assert_eq!(Solution::k_inverse_pairs(n, k), result);
}
}
// Accepted solution for LeetCode #629: K Inverse Pairs Array
function kInversePairs(n: number, k: number): number {
const f: number[] = Array(k + 1).fill(0);
f[0] = 1;
const s: number[] = 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];
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.