leetcode

commit f243a7fc3cdf5fc8ddce6998fd2f92381ed3068f
parent 5b4835a538e3d35db93d58b64e4e3b8bdf58affc
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 30 Jun 2023 17:37:33 +0200

Daily Problem

Diffstat:
A
Problems/1970.cpp
 | 
60
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
3
++-

2 files changed, 62 insertions(+), 1 deletion(-)
diff --git a/Problems/1970.cpp b/Problems/1970.cpp
@@ -0,0 +1,60 @@
+class UnionFind {
+  int root[20002], size[20002];
+
+public:
+  UnionFind() {
+    for (int i = 0; i < 20002; i++) {
+      root[i] = i;
+      size[i] = 1;
+    }
+  }
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (size[x] > size[y]) swap(x, y);
+      root[x] = y;
+      size[y] += size[x];
+    }
+  }
+
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+class Solution {
+  int grid[20000] = {0};
+
+public:
+  int latestDayToCross(int row, int col, const vector<vector<int>> &cells) {
+    static const auto index = [&](int i, int j) { return i * col + j; };
+    static const auto valid = [&](int i, int j) {
+      return i >= 0 && j >= 0 && i < row && j < col;
+    };
+    static const int offset_x[] = {0, 0, 1, -1};
+    static const int offset_y[] = {1, -1, 0, 0};
+
+    UnionFind uf;
+
+    for (int i = cells.size() - 1; i >= 0; i--) {
+      const int x = cells[i][0] - 1, y = cells[i][1] - 1, ind = index(x, y);
+      grid[ind] = true;
+
+      for (int k = 0; k < 4; k++) {
+        int i = x + offset_x[k], j = y + offset_y[k];
+        if (!valid(i, j) || !grid[index(i, j)]) continue;
+        uf.join(ind, index(i, j));
+      }
+
+      if (x == 0) uf.join(ind, 20000);
+      if (x == row - 1) uf.join(ind, 20001);
+      if (uf.connected(20000, 20001)) return i;
+    }
+
+    return row * col;
+  }
+};
diff --git a/README.md b/README.md
@@ -360,7 +360,7 @@ for solving problems.
 |  0844  |    Easy    | [Backspace String Compare](Problems/0844.cpp)                                                    |
 |  0851  |   Medium   | [Loud and Rich](Problems/0851.cpp)                                                               |
 |  0853  |   Medium   | [Car Fleet](Problems/0853.cpp)                                                                   |
-|  0864  |   Medium   | [Shortest Path to Get All Keys](Problems/0864.cpp)                                               |
+|  0864  |    Hard    | [Shortest Path to Get All Keys](Problems/0864.cpp)                                               |
 |  0872  |    Easy    | [Leaf-Similar Trees](Problems/0872.cpp)                                                          |
 |  0875  |   Medium   | [Koko Eating Bananas](Problems/0875.cpp)                                                         |
 |  0876  |    Easy    | [Middle of the Linked List](Problems/0876.cpp)                                                   |
@@ -522,6 +522,7 @@ for solving problems.
 |  1926  |   Medium   | [Nearest Exit from Entrance in Maze](Problems/1926.cpp)                                          |
 |  1962  |   Medium   | [Remove Stones to Minimize the Total](Problems/1962.cpp)                                         |
 |  1964  |    Hard    | [Find the Longest Valid Obstacle Course at Each Position](Problems/1964.cpp)                     |
+|  1970  |    Hard    | [Last Day Where You Can Still Cross](Problems/1970.cpp)                                          |
 |  1971  |    Easy    | [Find if Path Exists in Graph](Problems/1971.cpp)                                                |
 |  1976  |   Medium   | [Number of Ways to Arrive at Destination](Problems/1976.cpp)                                     |
 |  1991  |    Easy    | [Find the Middle Index in Array](Problems/1991.cpp)                                              |