629. K Inverse Pairs Array
Problem Description
The problem deals with counting the number of different arrays composed of numbers from 1
to n
in which there are exactly k
inverse pairs. An inverse pair in an array is a pair of indices [i, j]
such that i < j
and nums[i] > nums[j]
. You are asked to return this number modulo 10^9 + 7
to keep the number manageable and address potential integer overflow issues.
Intuition
The core idea behind the solution is dynamic programming. The challenge is to find a way to efficiently calculate the number of arrays with exactly k
inverse pairs for any n
. We maintain an array f
, where f[j]
represents the number of arrays that consist of numbers from 1
to the current i
and have exactly j
inverse pairs.
To build up the solution, we start from the simplest array i = 1
(which can only have zero inverse pairs, as it is a single element array) and iteratively calculate up to the size n
while keeping track of the count of inverse pairs.
For a given i
(current array size), the number of ways to form j
inverse pairs is incrementally built upon the number of ways to form fewer inverse pairs with a smaller array size (i-1
). We achieve this by considering the placement of the largest element i
. It can be inserted in i
different positions, each giving a different number of additional inverse pairs.
The secondary array s
, which is a prefix sum array of f
, helps in calculating the running sum in order to get the number of ways to form j
inverse pairs quickly without iterating through each possibility, which would be inefficient.
In summary, we use dynamic programming to build the answer iteratively, utilizing prefix sums to efficiently calculate the dynamic programming states for each array size and inverse pair count.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution utilizes dynamic programming, where we define f[j]
as the number of arrays with elements from 1
to i
that have j
inverse pairs.
To calculate f[j]
for bigger arrays, we consider each possible position to insert the largest element i
in our array (which has an impact on the number of inverse pairs). If we insert i
at the end, we do not create any new inverse pairs; if we insert it just before the last element, we create one new inverse pair, and so on. If we insert it at the start, we create i-1
new inverse pairs.
-
The solution starts with initializing
f
with1
at index0
and0
elsewhere, since there's only one way to arrange an array of one element (which cannot create inverse pairs). -
To simplify and optimize the computation of the cumulative number of ways to create a certain number of inverse pairs when we increase the size of the array, we create a prefix sum array
s
. Prefix sum arrays provide a way to calculate the sum of a range of elements in constant time, after an initial linear time preprocessing.
The key step is the iteration:
-
For each size
i
of the array, we fillf[j]
forj = 1
tok
. For a given number of inverse pairsj
, the number of arrays is the sum of arrays that can be obtained by inserting the new elementi
in all possible positions. This is computed as(s[j + 1] - s[max(0, j - (i - 1))]) % mod
. The terms[j + 1] - s[max(0, j - (i - 1))]
gives us the number of arrays, considering all insertion positions of the elementi
that would keep the number of inverse pairs at exactlyj
. -
We update the prefix sum array
s
in terms off
, ass[j] = (s[j - 1] + f[j - 1]) % mod
forj = 1
tok + 1
. By keeping the prefix sums up to date, the calculation of subsequentf[j]
remains efficient.
- Finally, we return
f[k]
as the answer which represents the number of arrays of sizen
with exactlyk
inverse pairs.
By using dynamic programming and prefix sums, we efficiently calculate the number of arrays with exactly k
inverse pairs in a way that's computationally feasible for large values of k
and n
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider n = 3
(arrays composed of numbers 1 to 3) and k = 1
(we want exactly one inverse pair).
We will maintain an array f
where f[j]
represents the number of arrays with elements from 1 to the current i
that have j
inverse pairs. We also use a prefix sum array s
.
-
Initialize
f
as[1, 0, 0, ...]
, because there's only one array[1]
with zero inverse pairs. -
For
i = 2
, we need to account for arrays of two elements (numbers1
and2
). There are two possible arrays:[1, 2]
and[2, 1]
. The first array has 0 inverse pairs, and the second one has 1 inverse pair. So we updatef
to be[1, 1]
forf[0]
andf[1]
respectively. The prefix sumss
would be[0, 1, 2]
. -
For
i = 3
, we need to account for arrays of three elements (numbers1
,2
, and3
). The largest number3
can be placed in:- Position 3 (no new inverse pairs). The prior arrays of two numbers that can be extended are
[1, 2]
and[2, 1]
. - Position 2 (one new inverse pair). The prior arrays of two numbers are
[1, 2]
. - Position 1 (two new inverse pairs). However, we want exactly
k = 1
inverse pair, so we don't consider this case forf[1]
.
- Position 3 (no new inverse pairs). The prior arrays of two numbers that can be extended are
The number of arrays with exactly one inverse pair for i = 3
can be formed by inserting 3
in the first two possible positions for both [1, 2]
and [2, 1]
. For [1, 2]
, we gain one inverse pair if we insert 3
in the second position, and for [2, 1]
, we don't gain any because we insert 3
at the end.
The updated f[1]
for i=3
is the sum of ways we can insert 3
in the array [1, 2]
with 0 inverse pairs to get 1 inverse pair (1 way), plus the number of ways we can insert it in [2, 1]
and remain with 1 inverse pair (1 way). So f[1]
becomes 2
.
We would now generate the new prefix sums s
for i = 3
based on the updated f
.
In the end, you look at f[1]
for the total number of arrays of size 3 with exactly one inverse pair. The answer for this example is f[1] = 2
, representing the arrays: [1, 3, 2]
and [2, 3, 1]
.
This is how the solution approach can be applied to keep track of the number of arrays of increasing sizes with exactly k
inverse pairs. For each i
, we consider how the newest element can be inserted to maintain or reach the desired k
inverse pairs and update f
and s
accordingly.
Solution Implementation
1class Solution:
2 def kInversePairs(self, n: int, k: int) -> int:
3 mod = 10**9 + 7 # Define the modulus value to keep numbers within integer bounds
4
5 # dp table representing the count of inverse pairs for the current number of integers
6 dp = [1] + [0] * k
7
8 # Prefix sum array for optimization of the inner loop. The size is k+2 for 1-indexed and ease of access
9 prefix_sum = [0] * (k + 2)
10
11 # Iterate through integers from 1 to n
12 for current_number in range(1, n + 1):
13 # Going through all possible counts of inverse pairs from 1 to k
14 for inverse_count in range(1, k + 1):
15 # Update the dp table by taking the count from the prefix_sum within the range
16 # The range corresponds to the valid inverse pair counts that can be formed with the current number
17 dp[inverse_count] = (prefix_sum[inverse_count + 1] -
18 prefix_sum[max(0, inverse_count - (current_number - 1))]) % mod
19
20 # Updating prefix_sum based on the updated dp table
21 for index in range(1, k + 2):
22 prefix_sum[index] = (prefix_sum[index - 1] + dp[index - 1]) % mod
23
24 # Returning the number of ways to form k inverse pairs with n integers
25 return dp[k]
26
1class Solution {
2
3 public int kInversePairs(int n, int k) {
4 final int MOD = 1000000007; // Define the modulus value for the operations to prevent overflow
5
6 // Array 'dp' will store the count of arrays that have exactly j inverse pairs
7 int[] dp = new int[k + 1];
8
9 // Array 'prefixSum' will be utilized to calculate the total count efficiently
10 int[] prefixSum = new int[k + 2];
11
12 dp[0] = 1; // Base case: one way to arrange with 0 inverse pairs (no pairs)
13 prefixSum[1] = 1; // Initialize the prefix sum for the base case
14
15 // Iterate from 1 to n to build the answer iteratively
16 for (int i = 1; i <= n; i++) {
17 for (int j = 1; j <= k; j++) {
18 // Compute the number of arrays that have exactly j inverse pairs
19 // by finding the difference of prefix sums, and then taking the modulus
20 int val = (prefixSum[j + 1] - prefixSum[Math.max(0, j - i)] + MOD) % MOD;
21 dp[j] = val;
22 }
23
24 // Update prefix sums for the next iteration
25 for (int j = 1; j <= k + 1; j++) {
26 prefixSum[j] = (prefixSum[j - 1] + dp[j - 1]) % MOD;
27 }
28 }
29
30 // Return the count of arrays that have exactly k inverse pairs
31 return dp[k];
32 }
33}
34
1class Solution {
2public:
3 int kInversePairs(int n, int k) {
4 vector<int> dp(k + 1, 0); // Use vector instead of C array for dynamic array, initialized with 0s.
5 vector<int> prefixSums(k + 2, 0); // Prefix sums array for dynamic programming optimization.
6 dp[0] = 1; // Base case - zero inverse pairs
7 prefixSums[1] = 1; // Base case for prefix sums - one way to have 0 inverse pairs.
8 const int MOD = 1e9 + 7; // Define the modulo constant.
9
10 // Iterate over all numbers from 1 to n.
11 for (int i = 1; i <= n; ++i) {
12 // Compute the number of ways to have j inverse pairs.
13 for (int j = 1; j <= k; ++j) {
14 // The number of ways to arrange i numbers with j inverse pairs, we update dp for the current number.
15 // We use prefix sums to calculate the range sum, which optimizes the computation from O(k) to O(1) time.
16 dp[j] = (prefixSums[j + 1] - prefixSums[max(0, j - i)] + MOD) % MOD;
17 }
18 // Update prefix sums after processing each number i.
19 for (int j = 1; j <= k + 1; ++j) {
20 prefixSums[j] = (prefixSums[j - 1] + dp[j - 1]) % MOD;
21 }
22 }
23 // Return the number of ways to arrange n numbers with exactly k inverse pairs.
24 return dp[k];
25 }
26};
27
1function kInversePairs(n: number, k: number): number {
2 // Initialize an array to store the number of ways to form arrays
3 const numWays: number[] = new Array(k + 1).fill(0);
4 numWays[0] = 1; // Base case: 0 inverse pairs
5
6 // Initialize the prefix sums array of numWays for efficient range sum queries
7 const prefixSums: number[] = new Array(k + 2).fill(1);
8 prefixSums[0] = 0; // Base case
9
10 // Define the modulus value to prevent integer overflow in calculations
11 const mod: number = 1e9 + 7;
12
13 // Iterate over the integers from 1 to n
14 for (let i = 1; i <= n; i++) {
15 // Iterate over the possible number of inverse pairs from 1 to k
16 for (let j = 1; j <= k; j++) {
17 // Calculate the number of ways to form j inverse pairs with i numbers.
18 // This is done by calculating the range sum from the prefix sum array and adjusting for the modulus.
19 numWays[j] = (prefixSums[j + 1] - prefixSums[Math.max(0, j - (i - 1))] + mod) % mod;
20 }
21
22 // Update the prefix sums array using the new values from numWays
23 for (let j = 1; j <= k + 1; j++) {
24 prefixSums[j] = (prefixSums[j - 1] + numWays[j - 1]) % mod;
25 }
26 }
27
28 // Return the total number of ways to form k inverse pairs with n numbers
29 return numWays[k];
30}
31
Time and Space Complexity
Time Complexity
The time complexity of the code is primarily determined by two nested loops. The outer loop runs for n
iterations, where n
represents the number of elements. The inner loop runs up to k
iterations for every outer loop iteration, where k
is the number of inverse pairs we want to find. This suggests that the overall time complexity is O(nk)
, as for each of the n
elements, we potentially examine every k
.
Space Complexity
The space complexity of the algorithm is determined by the storage used for the array f
and the prefix sum array s
. The array f
has a size of k + 1
and the array s
has a size of k + 2
. As k + 2
is the larger of the two, we can consider it for the space complexity estimation. The space complexity is, therefore, O(k)
because the amount of storage required increases linearly with k
.
Note that mod
and the loop counters such as i
and j
only use a constant amount of space and don't contribute significantly to the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!