leetcode

commit d992e1282953f53018a0cd3f4305a3e2c078b2fd
parent c3b4552a426ac28b674d0611e82b7a1295c8448a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 31 Jan 2023 15:53:14 +0100

LeetCode 75 I: Day 11

Diffstat:
A
Problems/0062.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/0062.cpp b/Problems/0062.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+  int uniquePaths(int n, int m) {
+    vector<vector<int>> mat(n, vector<int>(m, 0));
+    queue<pair<int, int>> q;
+    q.push({n - 1, m - 1}), mat[n - 1][m - 1] = 1;
+    while (!q.empty()) {
+      auto [x, y] = q.front();
+      q.pop();
+      if (x - 1 >= 0) {
+        mat[x - 1][y] += mat[x][y];
+        if (mat[x - 1][y] == mat[x][y]) q.push({x - 1, y});
+      }
+      if (y - 1 >= 0) {
+        mat[x][y - 1] += mat[x][y];
+        if (mat[x][y - 1] == mat[x][y]) q.push({x, y - 1});
+      }
+    }
+    return mat[0][0];
+  }
+};
diff --git a/README.md b/README.md
@@ -54,6 +54,7 @@ for solving problems.
 |  0057  |   Medium   | [Insert Interval](Problems/0057.cpp)                                                             |
 |  0059  |   Medium   | [Spiral Matrix II](Problems/0059.cpp)                                                            |
 |  0061  |   Medium   | [Rotate List](Problems/0061.cpp)                                                                 |
+|  0062  |   Medium   | [Unique Paths](Problems/0062.cpp)                                                                |
 |  0066  |    Easy    | [Plus One](Problems/0066.cpp)                                                                    |
 |  0067  |    Easy    | [Add Binary](Problems/0067.cpp)                                                                  |
 |  0070  |    Easy    | [Climbing Stairs](Problems/0070.cpp)                                                             |