Sponsored
Sponsored
This approach involves recursively dividing the grid into four quadrants until each subdivision is either uniform (composed of the same elements) or a minimum size is reached. The base case of the recursion is when the grid section being considered is uniform, guiding us to create a leaf node. Otherwise, you recursively create non-leaf nodes and divide the grid further.
Time Complexity: O(n^2 * log(n)), where n is the length of the grid. Each division checks floor(n^2) cells for uniformity.
Space Complexity: O(log(n)), due to the recursion stack depth.
1class Solution {
2 class Node {
3 public boolean val;
4 public boolean isLeaf;
5 public Node topLeft;
6 public Node topRight;
7 public Node bottomLeft;
8 public Node bottomRight;
9
10 public Node(boolean _val, boolean _isLeaf) {
11 this.val = _val;
12 this.isLeaf = _isLeaf;
13 }
14
15 public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
16 this.val = _val;
17 this.isLeaf = _isLeaf;
18 this.topLeft = _topLeft;
19 this.topRight = _topRight;
20 this.bottomLeft = _bottomLeft;
21 this.bottomRight = _bottomRight;
22 }
23 }
24
25 public Node construct(int[][] grid) {
26 return construct(grid, 0, 0, grid.length);
27 }
28
29 private Node construct(int[][] grid, int x, int y, int size) {
30 if (isUniform(grid, x, y, size)) {
31 return new Node(grid[x][y] == 1, true);
32 }
33 int half = size / 2;
34 Node topLeft = construct(grid, x, y, half);
35 Node topRight = construct(grid, x, y + half, half);
36 Node bottomLeft = construct(grid, x + half, y, half);
37 Node bottomRight = construct(grid, x + half, y + half, half);
38 return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
39 }
40
41 private boolean isUniform(int[][] grid, int x, int y, int size) {
42 int val = grid[x][y];
43 for (int i = x; i < x + size; i++) {
44 for (int j = y; j < y + size; j++) {
45 if (grid[i][j] != val) {
46 return false;
47 }
48 }
49 }
50 return true;
51 }
52}This Java solution follows the same logic as the Python solution, with similar methods for checking uniformity and recursively constructing the Quad-Tree structure, while handling Java-specific class and method definitions.
This approach involves using a queue data structure for constructing the Quad-Tree iteratively. Initially, you enqueue the entire grid with its coordinates. By dequeuing elements and checking uniformity, you either create a leaf node or enqueue its four sub-regions for further processing.
Time Complexity: O(n^2), as each entry in the grid must be visited to verify uniformity.
Space Complexity: O(n^2) in the worst case, since there's a possibility of storing every grid block in separate nodes.
1#include <iostream>
2#include <queue>
3#include <vector>
4
5using namespace std;
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft = nullptr;
Node* topRight = nullptr;
Node* bottomLeft = nullptr;
Node* bottomRight = nullptr;
Node(bool _val, bool _isLeaf) : val(_val), isLeaf(_isLeaf) {}
};
class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
int n = grid.size();
return construct(0, 0, n, grid);
}
private:
Node* construct(int x, int y, int size, vector<vector<int>>& grid) {
if (size == 1) {
return new Node(grid[x][y] == 1, true);
}
int half = size / 2;
Node* topLeft = construct(x, y, half, grid);
Node* topRight = construct(x, y + half, half, grid);
Node* bottomLeft = construct(x + half, y, half, grid);
Node* bottomRight = construct(x + half, y + half, half, grid);
if (topLeft->isLeaf && topRight->isLeaf && bottomLeft->isLeaf && bottomRight->isLeaf &&
topLeft->val == topRight->val && topRight->val == bottomLeft->val && bottomLeft->val == bottomRight->val) {
return new Node(topLeft->val, true);
}
return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
}
};The C++ solution utilizes an iterative technique by gradually processing nodes via a queue. Each iteration checks for uniform grids, constructing either leaf or non-leaf nodes, and breaks down non-uniform areas for further examination.