grid47 Exploring patterns and algorithms
Sep 25, 2024
7 min read
Solution to LeetCode 427: Construct Quad Tree Problem
You are given an n x n binary grid of 0’s and 1’s. Your task is to represent this grid with a Quad-Tree. A Quad-Tree is a tree structure where each node has four children. Each internal node has two properties: val (True for a grid of 1’s or False for a grid of 0’s) and isLeaf (True if the node is a leaf, False if it has children). If the entire grid has the same value, the node is a leaf. If not, the grid is divided into four sub-grids, and the process is repeated recursively for each sub-grid. Your goal is to return the root of the Quad-Tree that represents the grid.
Problem
Approach
Steps
Complexity
Input: The input consists of a grid, which is a 2D array of integers where each element is either 0 or 1. The grid is guaranteed to be a perfect square (n x n).
Example: [[0, 1], [1, 0]]
Constraints:
• 1 <= n <= 64
• grid is a 2D array of 0's and 1's
Output: The output is the root of the Quad-Tree that represents the input grid. The Quad-Tree is serialized using a level-order traversal where each node is represented as a list with two values: `[isLeaf, val]`. If the node is a leaf, isLeaf is 1, and the value `val` is either 1 for True or 0 for False. Internal nodes are represented with isLeaf 0 and any value for val.
Example: [[0, 1], [1, 0], [1, 1], [1, 1], [1, 0]]
Constraints:
Goal: The goal is to recursively divide the grid into four quadrants and create a tree structure where each node represents a square of the grid. If all elements in the square are the same, the node is a leaf; otherwise, it is an internal node with four children.
Steps:
• 1. Start with the whole grid.
• 2. If the grid is a 1x1 grid, return a leaf node.
• 3. If all elements of the grid are the same, return a leaf node with val set to that element's value.
• 4. Otherwise, split the grid into four sub-grids and recursively construct the Quad-Tree for each sub-grid.
• 5. If all four sub-grids have the same value, merge them into a single leaf node.
Goal: The input grid has size n x n where n is a power of 2.
Steps:
• 1 <= n <= 64
• Grid elements are either 0 or 1.
Assumptions:
• The grid is square and consists of only 0's and 1's.
• Explanation: This grid is split into four sub-grids. The top-left, bottom-left, and bottom-right sub-grids are uniform, while the top-right sub-grid has a mix of 1's and 0's. These sub-grids are further divided, leading to a Quad-Tree that efficiently represents the entire grid.
Approach: The approach to solving this problem involves recursively dividing the grid into smaller sub-grids and constructing the Quad-Tree based on the uniformity of the values in the sub-grids.
Observations:
• Each grid is divided into four quadrants at each step.
• If all elements of a sub-grid are the same, it can be represented as a leaf node.
• Recursive approach seems ideal, where we break down the grid into smaller grids and represent uniform grids as leaf nodes.
Steps:
• 1. Implement a helper function to recursively divide the grid.
• 2. Check if the sub-grid is uniform; if it is, return a leaf node.
• 3. If not, divide the grid further into four smaller grids and recursively build the tree.
Empty Inputs:
• A grid with all elements as 0 or all elements as 1 will immediately return a leaf node.
Large Inputs:
• If n is large, the recursive approach may encounter performance issues, so optimization or memoization might be needed.
Special Values:
• Grids with a single 0 or 1 will result in a very simple tree with just one node.
Constraints:
• Only grids with dimensions that are powers of 2 need to be considered.
Ensures that the values of all child nodes are equal before merging them.
12 : Set Leaf Node
res->val = topLeft->val;
Assigns the value of the child nodes to the parent node since all child nodes have the same value.
13 : Set Leaf Flag
res-> isLeaf =true;
Marks the current node as a leaf node because all child nodes were merged.
14 : Assign Children
res->topRight = topRight;
Assigns the top-right child to the current node when the children cannot be merged.
15 : Assign Children
res->topLeft = topLeft;
Assigns the top-left child to the current node when the children cannot be merged.
16 : Assign Children
res->bottomRight = bottomRight;
Assigns the bottom-right child to the current node when the children cannot be merged.
17 : Assign Children
res->bottomLeft = bottomLeft;
Assigns the bottom-left child to the current node when the children cannot be merged.
18 : Return Node
return res;
Returns the constructed node, which represents the current region of the grid.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: In the worst case, we need to examine all elements of the grid to determine if it can be represented as a leaf or needs further division.
Best Case: O(1)
Worst Case: O(n^2)
Description: The space complexity is driven by the recursion depth and the storage of the Quad-Tree nodes, which in the worst case can be proportional to the size of the grid.
