Leetcode Problem 629. K Inverse Pairs Array

629. K Inverse Pairs Array

Leetcode Solutions

Initialize a 1-D array dp of size k+1 with all elements set to 0.
Set dp[0] to 1, as there is exactly one arrangement with 0 inverse pairs (the sorted array).
Loop over the number of elements i from 1 to n: a. Create a temporary 1-D array temp of size k+1. b. Loop over the number of inverse pairs j from 0 to k: i. If j is less than i, set temp[j] to dp[j]. ii. If j is greater or equal to i, set temp[j] to dp[j] - dp[j-i] (if j-i is valid) plus dp[j]. c. Copy the temp array to the dp array.
Return dp[k] modulo 10^9 + 7 as the final answer.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen