algoadvance

Leetcode 558. Logical OR of Two Binary Grids Represented as Quad

Problem Statement

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

A Binary Grid is represented as a quad-tree. This problem involves computing the logical OR of two binary grids, which are given in the form of two quad-trees, and returning the resulting quad-tree.

A node in the quad-tree is represented as follows:

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

• val is the value of the node, which applies only if the node is a leaf (isLeaf is true).
• If the node is a leaf node, the value represents the value of that position in the grid (either 0 or 1).
• If the node is not a leaf, it has four children representing its four quadrants.

We are required to merge two quad-trees by logical OR operation. Return the resulting quad-tree.

Clarifying Questions

1. Can a node be entirely 0 or 1?
   • Yes, if a node is a leaf, it will have val=0 or val=1.
2. How should non-leaf nodes be represented in the result?
   • Non-leaf nodes will be represented by merging their children respectively with a logical OR operation.
3. What should we do if one tree is a leaf and the other is not?
   • If the tree with the leaf has val=1, the result will be the leaf node with val=1. If val=0, the result is the other tree structure.

Strategy

The strategy to solve this problem is by doing a recursive operation to merge the quad-trees:

1. If t1 or t2 (either of the input trees) is a leaf node:
   • If it is 1, return t1 or t2 (since OR any with 1 is 1).
   • If it is 0, return the other tree (since OR with 0 will be the other value).

2. If both nodes are not leaves, recursively merge their children nodes.

3. Combine the results of the children nodes into a new node. If all resultant children nodes are leaf nodes with the same value, flatten them to a single leaf node.

Code

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

public class Solution {
    public Node intersect(Node t1, Node t2) {
        if (t1.isLeaf) {
            if (t1.val) return t1;
            else return t2;
        }
        if (t2.isLeaf) {
            if (t2.val) return t2;
            else return t1;
        }

        Node topLeft = intersect(t1.topLeft, t2.topLeft);
        Node topRight = intersect(t1.topRight, t2.topRight);
        Node bottomLeft = intersect(t1.bottomLeft, t2.bottomLeft);
        Node bottomRight = intersect(t1.bottomRight, t2.bottomRight);

        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
            topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            return new Node(topLeft.val, true);
        }

        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

Time Complexity

The time complexity of the solution is O(min(n1, n2)), where n1 and n2 are the number of nodes in the two input quad-trees. In the worst case, we’ll need to traverse all nodes of the smaller tree to merge both trees.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?