LeetCode Solutions Blog

Logical OR of Two Binary Grids Represented as Quad-Trees

Difficulty: Medium

Problem Description

Given two Quad-Trees, quadTree1 and quadTree2, which represent two binary matrices, return a new Quad-Tree that represents the logical bitwise OR of the two binary matrices.

Key Insights

A Quad-Tree allows for efficient representation of binary matrices by dividing them into four quadrants.
The logical OR operation can be performed on two nodes by checking their properties (leaf or not) and combining their values accordingly.
If both nodes are leaves and have the same value, the result is the same value. If they differ, the result is a non-leaf node with children representing the logical OR of their respective quadrants.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the Quad-Trees since each node is processed once.
Space Complexity: O(n) for the space required to store the resulting Quad-Tree and the recursion stack.

Solution

The solution involves recursively traversing both Quad-Trees. For each pair of nodes, we check if they are leaves and combine their values accordingly. If one of the nodes is a leaf, we take its value, and if both are non-leaf nodes, we recursively process their children.

The data structure used is the Quad-Tree, and the algorithmic approach involves recursion and logical operations.

Code Solutions

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

def intersect(quadTree1, quadTree2):
    # If quadTree1 is a leaf node, return it if its value is True, otherwise return quadTree2
    if quadTree1.isLeaf:
        return quadTree1 if quadTree1.val else quadTree2
        
    # If quadTree2 is a leaf node, return it if its value is True, otherwise return quadTree1
    if quadTree2.isLeaf:
        return quadTree2 if quadTree2.val else quadTree1
    
    # Create a new node for the combined result
    newNode = Node()
    newNode.isLeaf = False
    newNode.val = True  # arbitrary value, will divide into quadrants
    
    # Recursively combine the quadrants
    newNode.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft)
    newNode.topRight = intersect(quadTree1.topRight, quadTree2.topRight)
    newNode.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
    newNode.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight)
    
    # If all four children are leaves with the same value, collapse into a single leaf node
    if (newNode.topLeft.isLeaf and newNode.topRight.isLeaf and 
        newNode.bottomLeft.isLeaf and newNode.bottomRight.isLeaf and
        newNode.topLeft.val == newNode.topRight.val == 
        newNode.bottomLeft.val == newNode.bottomRight.val):
        newNode.isLeaf = True
        newNode.val = newNode.topLeft.val
        
    return newNode