algoadvance

Leetcode 427. Construct Quad Tree

Problem Statement

Given a n * n matrix grid of 0s and 1s only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is True, and assign the children for a False node in the following order:

1. Top left child
2. Top right child
3. Bottom left child
4. Bottom right child

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s.
• isLeaf: a boolean value that is True if the node is a leaf node and False if it is an internal node.

We can construct a Quad-Tree from a two-dimensional area using the following steps:

1. If the current grid has the same value (all 1s or all 0s), set isLeaf to True and set val to the value of the grid, and set the four children to Null.
2. If the current grid has different values, set isLeaf to False and set val to any value, and divide the current grid into four sub-grids as shown in the problem description.

Clarifying Questions

1. Input Constraints:
   • What is the range of n?
   • Is n always a power of 2?

   Assumption: n is always a power of 2, making it easier to recursively divide the grid evenly.

2. Output:
   • The output should be a valid Quad-Tree structure representing the grid.

Strategy

1. Base Case:
   • If the entire grid has the same value, create a leaf node.
2. Recursive Division:
   • Divide the grid into four quadrants and recursively construct the Quad-Tree for each quadrant.
   • If all four children are leaves and have the same value, merge them into a single leaf node.
3. Node Structure:
   • Use a class Node to store val, isLeaf, and the four children (topLeft, topRight, bottomLeft, bottomRight).

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;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    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 construct(int[][] grid) {
        return construct(grid, 0, 0, grid.length);
    }

    private Node construct(int[][] grid, int row, int col, int length) {
        if (isUniform(grid, row, col, length)) {
            return new Node(grid[row][col] == 1, true);
        }
        
        int halfLength = length / 2;
        
        Node topLeft = construct(grid, row, col, halfLength);
        Node topRight = construct(grid, row, col + halfLength, halfLength);
        Node bottomLeft = construct(grid, row + halfLength, col, halfLength);
        Node bottomRight = construct(grid, row + halfLength, col + halfLength, halfLength);

        return new Node(
            false, 
            false, 
            topLeft, 
            topRight, 
            bottomLeft, 
            bottomRight
        );
    }
    
    private boolean isUniform(int[][] grid, int row, int col, int length) {
        int value = grid[row][col];
        for (int i = row; i < row + length; i++) {
            for (int j = col; j < col + length; j++) {
                if (grid[i][j] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}

Time Complexity

• Time Complexity: O(n^2 log n) where n is the width/height of the grid.
  • The isUniform check is O(n^2) for each level.
  • The recursion depth is log n.
• Space Complexity: O(log n) due to the recursion stack.

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?