<!--
<b>
-->

# <span style="color: orange">[Medium]</span> 3537. Fill a Special Grid

## Problem Summary
Given a number `n`, try to fill in a 2D list of `2ⁿ*2ⁿ` that following the given rule:
- All numbers in the top-right quadrant are smaller than those in the bottom-right quadrant.
- All numbers in the bottom-right quadrant are smaller than those in the bottom-left quadrant.
- All numbers in the bottom-left quadrant are smaller than those in the top-left quadrant.
- Each of its quadrants is also a special grid.

## 💡 Approach
The numbers are arranged in the format U, so for each n we try to wrap one more layer at the outside. To do that, we first create a list, going in as deep as possible, and fill the numbers following the given rule while <b>moving out layer by layer</b>. It is a <b>divide and conquer</b> concept so that for each time, we only have to deal with simple problems.

## </> Code

class Solution:
    def specialGrid(self, n: int) -> List[List[int]]:
        size = 2 ** n
        grid = [[0] * size for _ in range(size)]
        
        def fill_grid(sx, sy, size, num):
            # Edge case
            if size == 1:
                grid[sy][sx] = num
                return

            # Fill in the split grid
            half = size // 2
            new_num = (size * size) // 4
            fill_grid(sx, sy, half, num)
            fill_grid(sx, sy+half, half, num+new_num*1)
            fill_grid(sx-half, sy+half, half, num+new_num*2)
            fill_grid(sx-half, sy, half, num+new_num*3)
            return

        
        fill_grid(size-1, 0, size, 0)
        return grid

## 🕒 Runtime
Time: `182ms` | `Beats 50.50%`
Memory: `92.00MB` | `Beats 59.30%`

## 📈 Complexity

<b>Assume that: </b>
- `n` is the given number

<b>The overall complexity:</b>
- Time Complexity: `O(4ⁿ)`
- Space Complexity: `O(4ⁿ)+O(n)`