algoadvance

The problem is to construct a Quad-Tree representation of a given 2D matrix grid. A Quad-Tree is a tree data structure in which each internal node has exactly four children. The Quad-Tree is used to represent a two-dimensional spatial hierarchy.

The class QuadTreeNode should be defined as follows:

class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val  # represents whether the node is a leaf and the value 0/1 if it is a leaf
        self.isLeaf = isLeaf  # boolean value to indicate whether it's a leaf node
        self.topLeft = topLeft  # top left child
        self.topRight = topRight  # top right child
        self.bottomLeft = bottomLeft  # bottom left child
        self.bottomRight = bottomRight  # bottom right child

The construct function should be defined as follows:

def construct(grid: List[List[int]]) -> 'Node':

The function constructs a Quad-Tree for the given 2D matrix grid and returns the root of the Quad-Tree.

Clarifying Questions

  1. Grid Dimensions:
    • Can the grid be non-square? (Assuming it is always a power of 2 square for forming a balanced Quad-Tree)
  2. Values in Grid:
    • Are the values in the grid always either 0 or 1? (Assuming so)
  3. Empty Grid:
    • What should be the output if the grid is empty? (Assuming it won’t be empty given the constraints)

If these assumptions hold, we can proceed with solving the problem.

Strategy

  1. Base Case:
    • If the grid has only one element, create a leaf node with that element.
  2. Recursive Divide and Conquer:
    • For larger grids, divide the grid into four quadrants:
      • Top-left
      • Top-right
      • Bottom-left
      • Bottom-right
    • Recursively construct Quad-Trees for each quadrant.
    • If all four children are leaf nodes and have the same value, merge them into a single leaf node.
    • Otherwise, create a parent node with the four children.
  3. Helper Function:
    • Write a helper function to check if all elements in a given subgrid are the same. This helps in determining if a node should be a leaf.

Code

class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

def construct(grid):
    def isUniform(x, y, length):
        value = grid[x][y]
        for i in range(x, x + length):
            for j in range(y, y + length):
                if grid[i][j] != value:
                    return False, None
        return True, value

    def constructRecursively(x, y, length):
        is_uni, value = isUniform(x, y, length)
        if is_uni:
            return Node(value == 1, True)
        
        half = length // 2
        topLeft = constructRecursively(x, y, half)
        topRight = constructRecursively(x, y + half, half)
        bottomLeft = constructRecursively(x + half, y, half)
        bottomRight = constructRecursively(x + half, y + half, half)

        if (topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and
            topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
            return Node(topLeft.val, True)
        else:
            return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)

    n = len(grid)
    if n == 0:
        return None
    return constructRecursively(0, 0, n)

Time Complexity

Try our interview co-pilot at AlgoAdvance.com