algoadvance

Leetcode 427. Construct Quad Tree

Problem Statement

The problem number 427 on LeetCode is “Construct Quad Tree”. Here is the prompt:

We want to use quad trees to store an n x n boolean grid. Each cell in the grid is either 0 or 1. Quad trees are a type of tree structure where each internal node has exactly four children.

Each node in a quad tree has either a true value or a false value. For each node, if all the values in the region it represents are the same, then it is a leaf node, and its value indicates the value in that region. Otherwise, it is not a leaf node, and we need to be able to partition the region into four equal sub-regions and call the same process recursively for each of the regions.

You are given a n x n matrix grid representing a binary grid. Each cell is either 1 or 0. Write a function to construct the corresponding quad tree.

Quadtree Node Definition:

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;
    }
};

Clarifying Questions

  1. What are the possible dimensions for the provided grid?
    • The grid is an n x n matrix where n is a positive integer and a power of 2.
  2. What values can the cells of the grid contain?
    • The cells can contain either 0 or 1.
  3. Do the Node constructors and Node class already exist, or should they be implemented?
    • The Node constructors and the Node class are given as part of the problem definition and do not need to be implemented by you. You need to use them to construct your solution.
  4. What should be the return value of the constructed function?
    • The function should return the root of the Quad Tree.

Strategy

To solve this problem, we develop a recursive function to build the Quad Tree. The key steps are:

  1. Base Case: If the current region contains only one type of value (all 0s or all 1s), then we create a leaf node with this value.
  2. Divide & Conquer: Otherwise, we split the current region into four equal sub-regions and recursively construct the Quad Tree for each of them.
  3. Combine the results from the four sub-regions into a single node.

Code

Let’s implement the solution:

// 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* construct(vector<vector<int>>& grid) {
        return construct(grid, 0, 0, grid.size());
    }
    
private:
    Node* construct(vector<vector<int>>& grid, int r, int c, int size) {
        if (isUniform(grid, r, c, size)) {
            return new Node(grid[r][c] == 1, true);
        }
        
        int newSize = size / 4;
        return new Node(
            true, false,
            construct(grid, r, c, newSize),
            construct(grid, r, c + newSize, newSize),
            construct(grid, r + newSize, c, newSize),
            construct(grid, r + newSize, c + newSize, newSize)
        );
    }
    
    bool isUniform(vector<vector<int>>& grid, int r, int c, int size) {
        int val = grid[r][c];
        for (int i = r; i < r + size; ++i) {
            for (int j = c; j < c + size; ++j) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity

The time complexity of this recursive approach can be analyzed as follows:

Thus, combining these, the overall time complexity is O(n^2 * log(n)).

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