558. Logical OR of Two Binary Grids Represented as Quad-Trees

MediumTreeDivide and Conquer
Leetcode Link

Problem Description

In this problem, we are tasked with performing a logical OR operation on two binary matrices, both of which are represented by quad-trees. A binary matrix is a two-dimensional grid where each cell can either hold a 0 or a 1. A quad-tree is a special tree structure used to represent such a matrix, where each internal node represents a 2x2 block of cells and has four children that correspond to the four quadrants formed by dividing the block further. These are the topLeft, topRight, bottomLeft, and bottomRight children.

Each node of the quad-tree has two attributes: val, which indicates the value of the entire block (True for 1 and False for 0), and isLeaf, which is True if the node has no children and represents a single-cell block, or False if it does have children. A quad-tree node with isLeaf set to True means that the block has uniform values in all cells, either all 0s or all 1s.

The goal is to define a function that accepts two quad-trees and returns a new quad-tree which is the logical OR result of the two input matrices. The logical OR should be performed at the leaf nodes, with True (or 1) being the result if either of the corresponding blocks in the input matrices contains a 1.

Intuition

For solving this problem, we need to use recursion, as the structure of a quad-tree is inherently recursive. We can define a recursive function dfs to navigate through both trees simultaneously and apply the logical OR operation. The base cases of our recursive function are:

  1. When both nodes are leaves, we perform the OR of their val attributes and return a new leaf node with the result.
  2. When one node is a leaf and its value is True (1), we already know that no matter what the other node contains, the result of the OR operation will be True, so we return the true leaf node.
  3. If one node is a leaf and its value is False (0), the result will depend solely on the other node, so we return the other node.

For non-leaf nodes (i.e., nodes with children), we must apply the function recursively to each pair of children (topLeft with topLeft, topRight with topRight, etc.) to obtain the result for each quadrant. After the recursive step, we need to check whether the resulting children are all leaves and have the same value. If they are, we can collapse the four children into a single leaf node with that value. Otherwise, we keep the four children.

Therefore, the intuition behind the solution is to reduce the problem to simpler subproblems by recursively applying logical OR to corresponding nodes until we reach the leaves, then combine the results back up through the tree, potentially simplifying the structure where possible.

Learn more about Tree and Divide and Conquer patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution involves defining a recursive function named dfs that accepts two nodes from the given quad-trees and returns a new quad-tree representing the result of the logical OR operation between the sub-matrices represented by those nodes.

The algorithm uses the following steps:

  1. Base Cases:

    • If both t1 and t2 are leaves, return a new node with isLeaf set to True and val being the OR of t1.val and t2.val.
    • If t1 is a leaf and its val is True, then regardless of t2, the result will be True, so return t1.
    • If t2 is a leaf and its val is True, then regardless of t1, the result will be True, so return t2.
    • If t1 is a leaf and its val is False, then the result will be solely determined by t2, so return t2.
    • If t2 is a leaf and its val is False, then the result will be solely determined by t1, so return t1.

  2. Recursive Case:

    • If neither node is a leaf (both have children), then we create a new node res with isLeaf set to False and without setting val because we will determine its value by the values of its children.
    • We recursively call dfs on each pair of corresponding children and assign the results to the corresponding children of res.

  3. Post-Recursion Processing:

    • After the recursive calls, we need to check if res could eventually be collapsed into a leaf node:
      • Check if all children of res are leaves (with isLeaf set to True).
      • Check if all children of res have the same val.
    • If the above two conditions are met, res can actually represent the entire area with a single value, so we simplify it by replacing res with one of its children (which are all the same due to the checks).

By applying this recursive algorithm, we ensure that at each level of the trees, we only create new nodes when necessary and simplify the result as much as possible, which could potentially reduce the size of the resulting quad-tree compared to a naive combination of the two input quad-trees.

The algorithm effectively applies the logical OR on the two binary matrices and reflects the result in a quad-tree format, exploiting the quad-tree’s hierarchical nature for efficient processing.

In the solution code, the dfs function is called once with the roots of quadTree1 and quadTree2, kicking off the recursive process and eventually building the result quad-tree from the bottom up.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's consider two small binary matrices and walk through their OR operation using the quad-tree approach described in the solution.

1Matrix A:       Matrix B:
21 0             0 1
31 1             1 1
4
5Quad-Tree A:    Quad-Tree B:
6 N1: isLeaf=False
7   / | | \
8 N2 N3 N4 N5    N6: isLeaf=False
9 1  0  1  1      / | | \
10                N7 N8 N9 N10
11                0  1  1  1

For simplicity, let's assume that these matrices are already given in the form of quad-trees with each leaf node (N2-N5, N7-N10) representing a single cell of its respective matrix.

Let's compute the logical OR quad-tree step by step:

  1. Start the dfs function by passing the nodes N1 (root of Quad-Tree A) and N6 (root of Quad-Tree B).
  2. Since neither N1 nor N6 are leaves, create a new node, say R, with isLeaf set to False (representing the result quad-tree's root).

Next, apply dfs recursively on the children:

  1. Call dfs on N2 and N7.

    • Both are leaves, so compare their values.
    • The result for this quadrant is 1 OR 0 which equals 1.
    • Create a new leaf node, say R1, with val = True.

  2. Call dfs on N3 and N8.

    • Both are leaves, so 0 OR 1 equals 1.
    • Create a new leaf node, say R2, with val = True.

  3. Call dfs on N4 and N9.

    • Both are leaves, so 1 OR 1 equals 1.
    • Create a new leaf node, say R3, with val = True.

  4. Call dfs on N5 and N10.

    • Both are leaves, so 1 OR 1 equals 1.
    • Create a new leaf node, say R4, with val = True.

After the recursive calls, we have the following situation for R's children:

1R: isLeaf=False
2  / | | \
3R1 R2 R3 R4
41  1  1  1

All R's children (R1-R4) are leaves and have the same val of True. According to our algorithm, in such cases, we can collapse the node.

  1. Replace the node R with a single leaf node, say Rfinal, setting isLeaf to True and val to True.

The final quad-tree resulting from the logical OR of Quad-Tree A and Quad-Tree B is simply:

1Rfinal: isLeaf=True, val=True

This represents a uniform matrix where all values are 1, as expected from the OR operation on the given matrices.

Solution Implementation

1class Node:
2    def __init__(self, value, is_leaf, top_left, top_right, bottom_left, bottom_right):
3        self.value = value
4        self.is_leaf = is_leaf
5        self.top_left = top_left
6        self.top_right = top_right
7        self.bottom_left = bottom_left
8        self.bottom_right = bottom_right
9
10
11class Solution:
12    def intersect(self, quad_tree1: "Node", quad_tree2: "Node") -> "Node":
13        # Define a recursive function to traverse both quad trees
14        def traverse_nodes(node1, node2):
15            # If both nodes are leaves, return a new leaf node with OR result of values
16            if node1.is_leaf and node2.is_leaf:
17                return Node(node1.value or node2.value, True, None, None, None, None)
18          
19            # If either node is a leaf, return the filled one or the other node
20            if node1.is_leaf:
21                return node1 if node1.value else node2
22            if node2.is_leaf:
23                return node2 if node2.value else node1
24          
25            # Create a new intermediate node
26            result_node = Node(value=None, is_leaf=False, top_left=None, top_right=None, bottom_left=None, bottom_right=None)
27          
28            # Recursively traverse children nodes
29            result_node.top_left = traverse_nodes(node1.top_left, node2.top_left)
30            result_node.top_right = traverse_nodes(node1.top_right, node2.top_right)
31            result_node.bottom_left = traverse_nodes(node1.bottom_left, node2.bottom_left)
32            result_node.bottom_right = traverse_nodes(node1.bottom_right, node2.bottom_right)
33          
34            # Check if all children are leaf nodes and hold the same value
35            all_children_are_leaves = result_node.top_left.is_leaf and \
36                                      result_node.top_right.is_leaf and \
37                                      result_node.bottom_left.is_leaf and \
38                                      result_node.bottom_right.is_leaf
39            all_children_hold_same_value = all_children_are_leaves and \
40                                       (result_node.top_left.value ==
41                                        result_node.top_right.value ==
42                                        result_node.bottom_left.value ==
43                                        result_node.bottom_right.value)
44          
45            # Simplify tree by collapsing children nodes into a single leaf if possible
46            if all_children_hold_same_value:
47                result_node = Node(result_node.top_left.value, True, None, None, None, None)
48            return result_node
49
50        # Start the recursive process with the two given quad trees
51        return traverse_nodes(quad_tree1, quad_tree2)
52
1// Definition for a QuadTree node.
2class Node {
3    // Indicate the value of a leaf node (black or white).
4    public boolean val;
5    // Indicate if the node is a leaf.
6    public boolean isLeaf;
7    // Points to the top-left child of the node.
8    public Node topLeft;
9    // Points to the top-right child of the node.
10    public Node topRight;
11    // Points to the bottom-left child of the node.
12    public Node bottomLeft;
13    // Points to the bottom-right child of the node.
14    public Node bottomRight;
15
16    // Default constructor.
17    public Node() {}
18
19    // Constructor that initializes the node’s attributes.
20    public Node(boolean value, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
21        // Assign the nodes’s attributes.
22        val = value;
23        this.isLeaf = isLeaf;
24        this.topLeft = topLeft;
25        this.topRight = topRight;
26        this.bottomLeft = bottomLeft;
27        this.bottomRight = bottomRight;
28    }
29}
30
31class Solution {
32    // This function returns the intersection of two quadtrees.
33    public Node intersect(Node quadTree1, Node quadTree2) {
34        // Call the recursive DFS function to traverse the trees.
35        return dfs(quadTree1, quadTree2);
36    }
37
38    // Private helper function that performs DFS on the quadtrees to find the intersection.
39    private Node dfs(Node tree1, Node tree2) {
40        // If both nodes are leaves, return a new leaf node that carries the intersection of their values.
41        if (tree1.isLeaf && tree2.isLeaf) {
42            return new Node(tree1.val || tree2.val, true, null, null, null, null);
43        }
44        // If the first node is a leaf and its value is true, or the second node is a leaf and its value is true.
45        // Then return the node with the true value, as it takes precedence in the intersection.
46        if (tree1.isLeaf) {
47            return tree1.val ? tree1 : tree2;
48        }
49        if (tree2.isLeaf) {
50            return tree2.val ? tree2 : tree1;
51        }
52        // Create a new parent node for the result.
53        Node result = new Node();
54        // Recursively compute the intersection for each corresponding child.
55        result.topLeft = dfs(tree1.topLeft, tree2.topLeft);
56        result.topRight = dfs(tree1.topRight, tree2.topRight);
57        result.bottomLeft = dfs(tree1.bottomLeft, tree2.bottomLeft);
58        result.bottomRight = dfs(tree1.bottomRight, tree2.bottomRight);
59
60        // Check if all children are leaves and have the same value.
61        boolean allChildrenAreLeaves = result.topLeft.isLeaf && result.topRight.isLeaf && result.bottomLeft.isLeaf && result.bottomRight.isLeaf;
62        boolean allChildrenHaveSameValue = result.topLeft.val == result.topRight.val
63                && result.topRight.val == result.bottomLeft.val && result.bottomLeft.val == result.bottomRight.val;
64
65        // If all children are leaves and have the same value, the parent becomes a leaf node.
66        if (allChildrenAreLeaves && allChildrenHaveSameValue) {
67            result = new Node(result.topLeft.val, true, null, null, null, null);
68        }
69        return result; // Return the computed intersection node.
70    }
71}
72
1class Node {
2public:
3    bool value;
4    bool isLeaf;
5    Node* topLeft;
6    Node* topRight;
7    Node* bottomLeft;
8    Node* bottomRight;
9
10    // Constructor for a leaf node
11    Node(bool value, bool isLeaf) 
12         : value(value), isLeaf(isLeaf),
13           topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
14
15    // Constructor for a non-leaf node
16    Node(bool value, bool isLeaf, Node* topLeft, Node* topRight, Node* bottomLeft, Node* bottomRight)
17         : value(value), isLeaf(isLeaf),
18           topLeft(topLeft), topRight(topRight), bottomLeft(bottomLeft), bottomRight(bottomRight) {}
19};
20
21class Solution {
22public:
23    // Main function to intersect two quad trees
24    Node* intersect(Node* quadTree1, Node* quadTree2) {
25        return dfs(quadTree1, quadTree2);
26    }
27
28    // Helper function that performs depth-first search to find intersection of two trees
29    Node* dfs(Node* tree1, Node* tree2) {
30        // If both nodes are leaves, the result node should be a leaf with value OR of both
31        if (tree1->isLeaf && tree2->isLeaf) {
32            return new Node(tree1->value || tree2->value, true);
33        }
34
35        // If one of the nodes is a leaf, the result depends on the value of that leaf
36        if (tree1->isLeaf) {
37            return tree1->value ? tree1 : tree2;
38        }
39        if (tree2->isLeaf) {
40            return tree2->value ? tree2 : tree1;
41        }
42
43        // Recursive case: neither tree is a leaf. We must combine the children.
44        Node* result = new Node();
45        result->topLeft = dfs(tree1->topLeft, tree2->topLeft);
46        result->topRight = dfs(tree1->topRight, tree2->topRight);
47        result->bottomLeft = dfs(tree1->bottomLeft, tree2->bottomLeft);
48        result->bottomRight = dfs(tree1->bottomRight, tree2->bottomRight);
49
50        // Optimization: if all children are leaves and have the same value, merge them into one leaf
51        bool allChildrenAreLeaves = result->topLeft->isLeaf && result->topRight->isLeaf &&
52                                    result->bottomLeft->isLeaf && result->bottomRight->isLeaf;
53        bool allChildrenHaveSameValue = result->topLeft->value == result->topRight->value &&
54                                        result->topRight->value == result->bottomLeft->value &&
55                                        result->bottomLeft->value == result->bottomRight->value;
56
57        if (allChildrenAreLeaves && allChildrenHaveSameValue) {
58            bool unifiedValue = result->topLeft->value;
59            delete result->topRight;
60            delete result->bottomLeft;
61            delete result->bottomRight;
62            delete result;
63            result = new Node(unifiedValue, true);
64        }
65
66        return result;
67    }
68};
69
1// Define the interface for a Node, which represents a node in the quad tree.
2interface INode {
3  value: boolean;
4  isLeaf: boolean;
5  topLeft?: INode | null;
6  topRight?: INode | null;
7  bottomLeft?: INode | null;
8  bottomRight?: INode | null;
9}
10
11// Intersection function which acts as the public API to intersect two quad trees.
12function intersect(quadTree1: INode, quadTree2: INode): INode {
13  return depthFirstSearch(quadTree1, quadTree2);
14}
15
16// Helper function that performs depth-first search to find the intersection
17// of two quad trees by checking various conditions.
18function depthFirstSearch(tree1: INode, tree2: INode): INode {
19  // If both nodes are leaves, return a new leaf node with value being the OR of both values.
20  if (tree1.isLeaf && tree2.isLeaf) {
21    return { value: tree1.value || tree2.value, isLeaf: true };
22  }
23
24  // If one of the nodes is a leaf, use its value to decide which subtree to keep.
25  if (tree1.isLeaf) {
26    return tree1.value ? tree1 : tree2;
27  }
28  if (tree2.isLeaf) {
29    return tree2.value ? tree2 : tree1;
30  }
31
32  // If neither node is a leaf, proceed with combining the children of both nodes.
33  const result: INode = {
34    value: false, // Default value, will be changed later if needed
35    isLeaf: false,
36    topLeft: depthFirstSearch(tree1.topLeft!, tree2.topLeft!),
37    topRight: depthFirstSearch(tree1.topRight!, tree2.topRight!),
38    bottomLeft: depthFirstSearch(tree1.bottomLeft!, tree2.bottomLeft!),
39    bottomRight: depthFirstSearch(tree1.bottomRight!, tree2.bottomRight!)
40  };
41
42  // Check if all children are leaves and have the same value.
43  const allChildrenAreLeaves: boolean = result.topLeft!.isLeaf && result.topRight!.isLeaf &&
44                                       result.bottomLeft!.isLeaf && result.bottomRight!.isLeaf;
45  const allChildrenHaveSameValue: boolean = result.topLeft!.value === result.topRight!.value &&
46                                            result.topRight!.value === result.bottomLeft!.value &&
47                                            result.bottomLeft!.value === result.bottomRight!.value;
48
49  // If all children are leaves and have the same value, merge them into one leaf node.
50  if (allChildrenAreLeaves && allChildrenHaveSameValue) {
51    const unifiedValue: boolean = result.topLeft!.value;
52    return { value: unifiedValue, isLeaf: true };
53  }
54
55  // If the children are not all leaves or have different values, return the combined node.
56  return result;
57}
58
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

The given Python code defines the function intersect which merges two quad-trees. A quad-tree is a tree data structure in which each internal node has exactly four children.

Time Complexity:

The dfs (depth-first search) function is called recursively until all nodes in both quad-trees are visited. In the worst case, both quad-trees are full and have a height of h, and so there are 4^h nodes in each tree.

The time complexity of merging two nodes is O(1). In the worst case, we visit each pair of nodes once, so the overall time complexity is O(4^h) which is also expressed as O(n) where n is the number of nodes in the quad-tree if it is full.

Space Complexity:

The space complexity is mainly due to the recursive calls to the dfs function on the stack. In the worst case, the stack could have O(h) calls where h is the height of the tree, and since h = log4(n) for a full quad-tree (n is the total number of nodes), the space complexity would be O(log(n)). There is also additional space used to create new nodes when merging. However, this does not exceed O(n) since it will just be recreating the resultant quad-tree.

Therefore, the space complexity is O(log(n)) due to recursion, though it should be noted that this does not include the space required for the result tree itself.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫