K Inverse Pairs Array solution and explanation
Google
9 more videos on this problem
K Inverse Pairs Array - Leetcode 629 - PythonNeetCodeIO · 29:44 · 19K views
K Inverse Pairs Array | Leetcode 629 | Live coding session | DP Nailed!Coding Decoded · 14:14 · 11K views
K Inverse Pairs Array | Recursion | Memoization | Bottom Up | Optimal Bottom Up | Leetcode 629codestorywithMIK · 59:48 · 10K views
629. K Inverse Pairs Array | DP + Sliding Window | Recursion to Bottom Up Optimised ++Aryan Mittal · 45:50 · 6K views
K Inverse Pairs Array | LeetCode 629 | Coders CampCoders Camp · 16:25 · 2K views
LeetCode 629. K Inverse Pairs ArrayHappy Coding · 26:26 · 2K views
Leetcode - K Inverse Pairs Array (Python)Timothy H Chang · 15:23 · 1K views
Daily Leetcode #838: Jul 17, 2022 - 629. K Inverse Pairs ArrayProgramming Live with Larry · 43:54 · 816 views
LeetCode 629. K Inverse Pairs Array - HardLearn with EmKay · 22:31 · 685 views
K Inverse Pairs Array || Leetcode Hard 629 || Dynamic ProgrammingDigital Interview · 12:14 · 579 views
The problem
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 <= 1000
Approach overview
Problem Overview: Given integers n and k, count how many permutations of numbers 1..n contain exactly k inverse pairs. An inverse pair exists when i < j but nums[i] > nums[j]. The result can be very large, so the answer is returned modulo 1e9 + 7.
Approach 1: Dynamic Programming (Naive Transition) (Time: O(n*k*n), Space: O(n*k))
Define dp[i][j] as the number of arrays formed using numbers 1..i that contain exactly j inverse pairs. When inserting the number i into a permutation of size i-1, placing it at different positions creates additional inverse pairs. If you place i at position p from the end, it contributes p new inverse pairs. The transition becomes dp[i][j] = sum(dp[i-1][j-x]) for all valid x where 0 ≤ x < i. This directly simulates every possible insertion position, but the nested summation makes the time complexity O(n*k*n), which is too slow for large inputs.
Approach 2: Dynamic Programming with Prefix Sum Optimization (Time: O(n*k), Space: O(n*k))
The key observation is that the recurrence above repeatedly sums overlapping ranges. Instead of recomputing each sum, maintain a prefix sum over the previous row. This converts the transition into a constant-time range query: dp[i][j] = prefix[j] - prefix[j-i] (when j ≥ i). While iterating through j, maintain cumulative sums to build the next row efficiently. This removes the inner loop and reduces complexity to O(n*k). The technique is a classic optimization in dynamic programming where range-sum transitions are replaced with prefix sums. Modular arithmetic ensures values stay within limits.
This DP effectively models how permutations grow as the largest element is inserted into smaller permutations. Instead of enumerating permutations, it counts configurations mathematically. The prefix-sum trick transforms a cubic-style transition into a linear one over k, which is necessary for constraints up to n = 1000.
Recommended for interviews: The optimized DP with prefix sums is the expected solution. Interviewers often accept the basic DP recurrence first because it shows you understand how inverse pairs change when inserting elements. The optimized O(n*k) version demonstrates stronger mastery of dynamic programming transitions and range-sum optimization techniques commonly used in combinatorics-style counting problems.
Approach 1: Dynamic Programming Approach
We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.
def kInversePairs(n, k):
MOD = 1000000007
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for j in range(1, k + 1):
if i > 0:
dp[i][j] = (dp[i-1][j] + MOD - (dp[i-1][j-i] if j >= i else 0)) % MOD
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD
return (dp[n][k] + MOD - (dp[n][k-1] if k > 0 else 0)) % MOD
n = 3
k = 1
print(kInversePairs(n, k))public class KInversePairs {
public int kInversePairs(int n, int k) {
final int MOD = 1000000007;
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
for (int j = 1; j <= k; j++) {
if (i > 0) {
dp[i][j] = (dp[i-1][j] + MOD - (j >= i ? dp[i-1][j-i] : 0)) % MOD;
}
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
}
}
return (dp[n][k] + MOD - (k > 0 ? dp[n][k-1] : 0)) % MOD;
}
public static void main(String[] args) {
int n = 3, k = 1;
KInversePairs kip = new KInversePairs();
System.out.println(kip.kInversePairs(n, k));
}
}#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007
int kInversePairs(int n, int k) {
vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
for (int j = 1; j <= k; ++j) {
if (i == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = (dp[i-1][j] + MOD - (j>=i ? dp[i-1][j-i] : 0)) % MOD;
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
}
}
}
return (dp[n][k] + MOD - (k>0 ? dp[n][k-1] : 0)) % MOD;
}
int main() {
int n = 3, k = 1;
cout << kInversePairs(n, k) << endl;
return 0;
}function kInversePairs(n, k) {
const MOD = 1000000007;
const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
for (let j = 1; j <= k; j++) {
if (i > 0) {
dp[i][j] = (dp[i-1][j] + MOD - (j >= i ? dp[i-1][j-i] : 0)) % MOD;
}
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
}
}
return (dp[n][k] + MOD - (k > 0 ? dp[n][k-1] : 0)) % MOD;
}
const n = 3, k = 1;
console.log(kInversePairs(n, k));#include <stdio.h>
#define MOD 1000000007
int kInversePairs(int n, int k) {
int dp[n+1][k+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = 0;
if (i > 0) {
dp[i][j] = (dp[i-1][j] + MOD - (j>=i ? dp[i-1][j-i] : 0)) % MOD;
}
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
}
}
}
return (dp[n][k] + MOD - (k>0 ? dp[n][k-1] : 0)) % MOD;
}
int main() {
int n = 3, k = 1;
printf("%d\n", kInversePairs(n, k));
return 0;
}using System;
class KInversePairs {
public int kInversePairs(int n, int k) {
int MOD = 1000000007;
int[,] dp = new int[n + 1, k + 1];
for (int i = 0; i <= n; i++) {
dp[i, 0] = 1;
for (int j = 1; j <= k; j++) {
if (i > 0) {
dp[i, j] = (dp[i-1, j] + MOD - (j >= i ? dp[i-1, j-i] : 0)) % MOD;
}
dp[i, j] = (dp[i, j] + dp[i, j-1]) % MOD;
}
}
return (dp[n, k] + MOD - (k > 0 ? dp[n, k-1] : 0)) % MOD;
}
static void Main() {
int n = 3, k = 1;
KInversePairs kip = new KInversePairs();
Console.WriteLine(kip.kInversePairs(n, k));
}
}The Python solution uses nested loops to fill the DP table with initial values followed by recursive updates based on previous results. Lists handle dynamic allocation and data storage, and modulo ensures numerical stability.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
Approach 2: Dynamic Programming + Prefix Sum
We define f[i][j] as the number of arrays of length i with j inverse pairs. Initially, f[0][0] = 1, and the rest f[i][j] = 0.
Next, we consider how to obtain f[i][j].
Assume the first i-1 numbers are already determined, and now we need to insert the number i. We discuss the cases of inserting i into each position:
- If
iis inserted into the 1st position, the number of inverse pairs increases byi-1, sof[i][j] += f[i-1][j-(i-1)]. - If
iis inserted into the 2nd position, the number of inverse pairs increases byi-2, sof[i][j] += f[i-1][j-(i-2)]. - ...
- If
iis inserted into the(i-1)th position, the number of inverse pairs increases by 1, sof[i][j] += f[i-1][j-1]. - If
iis inserted into theith position, the number of inverse pairs does not change, sof[i][j] += f[i-1][j].
Therefore, f[i][j] = sum_{k=1}^{i} f[i-1][j-(i-k)].
We notice that the calculation of f[i][j] actually involves prefix sums, so we can use prefix sums to optimize the calculation process. Moreover, since f[i][j] only depends on f[i-1][j], we can use a one-dimensional array to optimize the space complexity.
The time complexity is O(n times k), and the space complexity is O(k). Here, n and k are the array length and the number of inverse pairs, respectively.
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];
}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]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n*k) |
| Dynamic Programming + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Naive Transition) | O(n*k*n) | O(n*k) | Useful for understanding how inserting the largest element affects inverse pairs |
| Dynamic Programming with Prefix Sum Optimization | O(n*k) | O(n*k) | Best general solution for large constraints and interview settings |
Frequently asked questions
Is K Inverse Pairs Array easy or hard?
LeetCode classifies K Inverse Pairs Array as a Hard problem. The challenge comes from deriving the DP recurrence and recognizing the prefix sum optimization required to reduce the complexity to O(n*k).
K Inverse Pairs Array Python/Java solution
Most implementations use the same DP recurrence with prefix sums. Python, Java, C++, JavaScript, and C# solutions maintain a DP table and compute each row using cumulative sums while applying modulo 1e9+7 to prevent overflow.
How to solve K Inverse Pairs Array in O(n*k)?
Use dynamic programming where dp[i][j] counts permutations of size i with j inverse pairs. Maintain prefix sums of the previous DP row so the transition dp[i][j] = prefix[j] - prefix[j-i] can be computed in constant time. This removes the inner loop and reduces complexity to O(n*k).
What is the best approach for K Inverse Pairs Array?
The most efficient method uses dynamic programming with prefix sum optimization. Define dp[i][j] as the number of permutations of size i with j inverse pairs. Using prefix sums allows each transition to be computed in constant time, giving an overall complexity of O(n*k).
Is K Inverse Pairs Array asked at Google/Amazon/Meta?
Inverse pair counting and permutation DP problems appear in interviews at companies like Google and Amazon. Variants focusing on counting permutations with constraints are common in algorithm-heavy interviews that test dynamic programming and combinatorics reasoning.
What data structure is used in K Inverse Pairs Array?
The core structure is a 2D dynamic programming table where rows represent the number of elements and columns represent inverse pair counts. Prefix sum arrays are used to optimize the DP transitions and avoid repeated range summations.
What is the time complexity of K Inverse Pairs Array?
The optimized dynamic programming solution runs in O(n*k) time and O(n*k) space. A straightforward DP transition without optimization takes O(n*k*n) time because it sums up to i previous states for every dp[i][j].