We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Logical OR of Two Binary Grids Represented as Quad-Trees

Number: 773

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two Quad-Trees representing n×n binary matrices (where each grid cell is 0 or 1), return a Quad-Tree representing the binary matrix formed by performing a logical (bitwise) OR on the two input matrices. Each Quad-Tree node has two attributes: isLeaf (indicating if the node is a leaf) and val (the value represented by the node if it is a leaf). In non-leaf nodes, the value can be arbitrary, and the node has four children corresponding to the four quadrants of the grid.

Key Insights

  • If either node is a leaf with a value of True (1), the OR result for that region is True.
  • If one node is a leaf with value False (0), then the result for that region is determined entirely by the other node.
  • If both nodes are not leaves, merge their corresponding children regions recursively.
  • After combining the four children, if all are leaves with the same value, the node can be compressed into a leaf.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario where every cell is represented by a separate leaf. Space Complexity: O(n^2) in the worst-case scenario due to the recursive call stack and the space used to hold the tree nodes.

Solution

The approach is to use recursion to merge the two Quad-Trees. At each recursive call:

  1. If one of the nodes is a leaf:
    • If its value is True, immediately return a new leaf node with True since True OR anything is True.
    • If its value is False, return the other node because False OR node == node.
  2. If neither node is a leaf, recursively merge the corresponding children: topLeft, topRight, bottomLeft, and bottomRight.
  3. After obtaining the merged children:
    • Check if all four children are leaves and have the same value.
    • If yes, compress them into a single leaf node with that value.
    • Otherwise, create a non-leaf node with these four children. The solution leverages divide and conquer by processing each quadrant independently and merging the results.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val            # True if region is 1's, False otherwise.
        self.isLeaf = isLeaf      # Boolean indicating whether the node is a leaf.
        self.topLeft = topLeft    # Top left child
        self.topRight = topRight  # Top right child
        self.bottomLeft = bottomLeft  # Bottom left child
        self.bottomRight = bottomRight  # Bottom right child

def intersect(node1, node2):
    # If the first node is a leaf.
    if node1.isLeaf:
        # If node1 represents True, OR with any value yields True.
        if node1.val:
            return Node(True, True)
        else:
            # If node1 is False, result depends solely on node2.
            return node2

    # Similarly, if the second node is a leaf.
    if node2.isLeaf:
        if node2.val:
            return Node(True, True)
        else:
            return node1

    # Recursively merge the four quadrants.
    topLeft = intersect(node1.topLeft, node2.topLeft)
    topRight = intersect(node1.topRight, node2.topRight)
    bottomLeft = intersect(node1.bottomLeft, node2.bottomLeft)
    bottomRight = intersect(node1.bottomRight, node2.bottomRight)

    # If all children are leaves and have the same value, compress them into one leaf node.
    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)
    
    # Otherwise, create a non-leaf node with these children.
    return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)
← Back to All Questions