algoadvance

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

Problem Statement

A Binary Grid is a grid where each cell is either 0 or 1. A Quad-Tree is a tree data structure with at most four children. Each node in this tree represents a rectangular sub-grid of a binary grid. The root node represents the entire binary grid, and for any node representing some sub-grid, its four children represent the four quadrants of that sub-grid.

Given two binary grids represented by two Quad-Trees, return a Quad-Tree which represents the logical OR (or union) of the two grids.

Each Quad-Tree node has the following attributes:

• bool val: True if the node represents a grid of 1’s, and False if it represents a grid of 0’s.
• bool isLeaf: True if the node is a leaf node, and False if the node has four children nodes in the tree.
• Node* topLeft, Node* topRight, Node* bottomLeft, Node* bottomRight: These are the four children of the current node.

Note:

• Both input trees are guaranteed to cover the same region.
• The logical OR of two grids results in a grid where each cell is 1 if either of the corresponding cells in the input grids is 1, otherwise 0.

Clarifying Questions

1. What should the output Quad-Tree represent?
   • The output Quad-Tree should represent a grid resulting from the logical OR operation on the input binary grids.
2. Are there any size constraints on the input grids?
   • No specific size constraints are provided other than that both trees cover the same region.

Strategy

1. If one of the nodes is a leaf and its value is True (1), the result will be a leaf with True since the OR operation with any value and True yields True.
2. If a node is a leaf and its value is False (0), the result will depend entirely on the other node.
3. If both nodes are non-leaf nodes, recursively compute the logical OR for each of the corresponding children (top-left, top-right, bottom-left, bottom-right).
4. If after merging all children, all are leaves and have the same value, compress them into a single leaf node.

Code

Here’s the C++ implementation:

#include <iostream>

// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {}

    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};

class Solution {
public:
    Node* intersect(Node* quadTree1, Node* quadTree2) {
        if (quadTree1->isLeaf) {
            return quadTree1->val ? new Node(true, true) : quadTree2;
        }
        if (quadTree2->isLeaf) {
            return quadTree2->val ? new Node(true, true) : quadTree1;
        }
        
        // Recursive call for each quadrant
        Node* topLeft = intersect(quadTree1->topLeft, quadTree2->topLeft);
        Node* topRight = intersect(quadTree1->topRight, quadTree2->topRight);
        Node* bottomLeft = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
        Node* bottomRight = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
        
        // If all four children are leaves and have the same value, merge them into one leaf node
        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

• Worst-Case Time Complexity: O(n), where n is the total number of nodes in the Quad-Tree. This is because the algorithm must potentially visit each node in both trees, resulting in a linear scan.
• Space Complexity: O(log n) due to the recursion stack used by the algorithm, as it follows the depth of the Quad-Tree.

By following this approach, we ensure that the logical OR of two Quad-Trees is computed efficiently and accurately.

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?