Problem statement

https://leetcode.com/problems/construct-quad-tree/

Solution

Basically do, what is asked to do: on each step check if all elements are equal, and if not, run recursion. Time complexity of this approach is O(n^2 log n), because equation is $T(n) = 4\cdot T(n/2) + O(n^2)$.

We can also do it in O(n^2) time if we use helper dfs function: to evaluate if for some sub-array all elements are equal we need to check if they are equal for 4 parts and also check that they are equal to each other. I use dfs(x1, y1, x2, y2) function, and return leaf if x2 = x1 + 1. Then recursively call function 4 times and if we have all 4 children which are leafs and they have equal value, we return Node(val, 1, None, None, None, None), so we can say we delete links to previous leafs. If not all children are leafs or they have different values, return Node(1, 0, N1, N2, N3, N4), where N1, N2, N3, N4 are recursively called function for 4 sub-arrays.

Complexity

Time complexity is O(n^2), space is O(n^2) as well.

Code

class Solution:
    def construct(self, grid):
        def dfs(x1, y1, x2, y2):
            if x2 - x1 == 1: 
                return Node(grid[x1][y1], 1, None, None, None, None)

            xm, ym = (x1+x2)//2, (y1+y2)//2

            N1 = dfs(x1, y1, xm, ym)
            N2 = dfs(x1, ym, xm, y2)
            N3 = dfs(xm, y1, x2, ym)
            N4 = dfs(xm, ym, x2, y2)

            isLeafNew = N1.isLeaf and N2.isLeaf and N3.isLeaf and N4.isLeaf
            isEqual = N1.val==N2.val and N2.val==N3.val and N3.val == N4.val

            if isLeafNew and isEqual:
                return Node(N1.val, 1, None, None, None, None)
            else:
                return Node(1, 0, N1, N2, N3, N4)
        
        return dfs(0, 0, len(grid), len(grid))