leetcode

commit 0613ea4cc53b05b6f762bd04febe9fc59eb735b9
parent 2f18129279bd6ce294c359c5bde7929d1ef77865
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 27 Jan 2024 20:31:03 +0000

Daily Problem

Diffstat:
A
Problems/0629.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0629.cpp b/Problems/0629.cpp
@@ -0,0 +1,38 @@
+class Solution {
+    static const int MOD = 1E9 + 7;
+
+  public:
+    int kInversePairs(int n, int k) {
+        static int dp[1001][1001];
+        memset(dp, 0x00, sizeof(dp));
+
+        dp[0][0] = 1;
+        for (int i = 1; i <= n; i++) {
+            for (int j = 0; j <= k; j++) {
+                dp[i][j] = (dp[i - 1][j] + (j > 0 ? dp[i][j - 1] : 0)) % MOD;
+                if (j >= i) dp[i][j] = (MOD + dp[i][j] - dp[i - 1][j - i]) % MOD;
+            }
+        }
+        return dp[n][k];
+    }
+};
+
+// Space optimized
+class Solution {
+    static const int MOD = 1E9 + 7;
+
+  public:
+    int kInversePairs(int n, int k) {
+        static int dp[2][1001];
+        memset(dp, 0x00, sizeof(dp));
+
+        dp[0][0] = 1;
+        for (int i = 1; i <= n; i++) {
+            for (int j = 0; j <= k; j++) {
+                dp[i % 2][j] = (dp[(i - 1) % 2][j] + (j > 0 ? dp[i % 2][j - 1] : 0)) % MOD;
+                if (j >= i) dp[i % 2][j] = (MOD + dp[i % 2][j] - dp[(i - 1) % 2][j - i]) % MOD;
+            }
+        }
+        return dp[n % 2][k];
+    }
+};
diff --git a/README.md b/README.md
@@ -407,6 +407,7 @@ for solving problems.
 |  0623  |   Medium   | [Add One Row to Tree](Problems/0623.cpp)                                                           |
 |  0626  |   Medium   | [Exchange Seats](Problems/0626.cpp)                                                                |
 |  0627  |    Easy    | [Swap Salary](Problems/0627.cpp)                                                                   |
+|  0629  |    Hard    | [K Inverse Pairs Array](Problems/0629.cpp)                                                         |
 |  0636  |   Medium   | [Exclusive Time of Functions](Problems/0636.cpp)                                                   |
 |  0637  |    Easy    | [Average of Levels in Binary Tree](Problems/0637.cpp)                                              |
 |  0641  |   Medium   | [Design Circular Deque](Problems/0641.cpp)                                                         |