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.
1function Node(val, isLeaf, topLeft, topRight,
This JavaScript solution mirrors the iterative approach by using ternary tree nodes. It handles grid divisions through iterative checks to determine if a section needs further breakdown, organizing components via nested loops.