leetcode

commit 1c8546dddabe78e4617ec7df4ab08854b1090f7c
parent 78e18e6b449d43415e3f1f4ef5e1c360ea33a899
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 27 Feb 2023 21:23:15 +0100

Daily Problem

Diffstat:
A
Problems/0427.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/0427.cpp b/Problems/0427.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+  Node *construct(vector<vector<int>> &grid, int rowStart, int rowEnd,
+                  int colStart, int colEnd) {
+    if (rowStart > rowEnd || colStart > colEnd) return nullptr;
+
+    bool isLeaf = true;
+    int val = grid[rowStart][colStart];
+    for (int i = rowStart; i <= rowEnd; i++) {
+      for (int j = colStart; j <= colEnd; j++) {
+        if (grid[i][j] != val) {
+          isLeaf = false;
+          break;
+        }
+      }
+      if (!isLeaf) break;
+    }
+
+    if (isLeaf) return new Node(val, true);
+
+    int rowMid = (rowStart + rowEnd) / 2;
+    int colMid = (colStart + colEnd) / 2;
+    Node *topLeft = construct(grid, rowStart, rowMid, colStart, colMid);
+    Node *topRight = construct(grid, rowStart, rowMid, colMid + 1, colEnd);
+    Node *bottomLeft = construct(grid, rowMid + 1, rowEnd, colStart, colMid);
+    Node *bottomRight = construct(grid, rowMid + 1, rowEnd, colMid + 1, colEnd);
+    return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
+  }
+  Node *construct(vector<vector<int>> &grid) {
+    int n = grid.size();
+    return construct(grid, 0, n - 1, 0, n - 1);
+  }
+};
diff --git a/README.md b/README.md
@@ -464,4 +464,5 @@ for solving problems.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 |  2497  |   Medium   | [Maximum Star Sum of a Graph](Problems/2497.cpp)                                                 |
+|  0427  |   Medium   | [Construct Quad Tree](Problems/0427.cpp)                                                 |