Leetcode Problem 629. K Inverse Pairs Array

629. K Inverse Pairs Array

Leetcode Solutions

Approach:-D Dynamic Programming

  1. Initialize a 1-D array dp of size k+1 with all elements set to 0.
  2. Set dp[0] to 1, as there is exactly one arrangement with 0 inverse pairs (the sorted array).
  3. 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.
  4. Return dp[k] modulo 10^9 + 7 as the final answer.
UML Thumbnail

Approach: Using Recursion with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...