Medium

Fill a Special Grid

LAB

For a 2^n by 2^n grid, return the canonical recursive fill order flattened row-major.

EXAMPLES

Example 1

Input
{
  "n": 1
}

Output
[
  0,
  2,
  3,
  1
]

FUNCTION SHAPE

n: int→intArray

SOLUTION NOTE

I think the best way to explain this is to look at the examples. It's clear that the top right will be 0, bottom right 1, and it will increment in a clockwise fashion. Think about how we build n=2 case from n=1 case. The top right quadrant for n=2 is just n=1. The bottom right is just n=1, but everything is incremented by 4, which is the number of elements in n=1. Similarly, for bottom_left and top_left. Now it's just a question of how do we merge these 4 quadrants into one? You can see we just construct top and bottom and concatenate them, and then finally increment all values in res by offset.

This is T(n) = 4 * T(n//4) + O(n) = O(nlogn) time.

Reveal reference solution +

pythonREFERENCE

def specialGrid(self, N: int) -> List[List[int]]:
    def dp(n, offset):
        if n == 0:
            return [[offset]]

        sz = 2 ** (2*(n-1))
        top_right = dp(n-1, 0)
        bottom_right = dp(n-1, sz)
        bottom_left = dp(n-1, 2 * sz)
        top_left = dp(n-1, 3 * sz)

        top = [a + b for a, b in zip(top_left, top_right)]
        bottom = [a + b for a, b in zip(bottom_left, bottom_right)]
        res = top + bottom

        for i in range(len(res)):
            for j in range(len(res[0])):
                res[i][j] += offset

        return res

    return dp(N, 0)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗