Skip to content

3537. Fill a Special Grid 👍

  • Time: $O(2^n \cdot 2^n)$
  • Space: $O(2^n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<vector<int>> specialGrid(int n) {
    const int sz = 1 << n;
    int count = 0;
    vector<vector<int>> grid(sz, vector<int>(sz));
    fill(grid, 0, sz, 0, sz, count);
    return grid;
  }

  void fill(vector<vector<int>>& grid, int x1, int x2, int y1, int y2,
            int& count) {
    if (x2 - x1 == 1) {
      grid[x1][y1] = count++;
      return;
    }
    const int midRow = (x1 + x2) / 2;
    const int midCol = (y1 + y2) / 2;
    fill(grid, x1, midRow, midCol, y2, count);
    fill(grid, midRow, x2, midCol, y2, count);
    fill(grid, midRow, x2, y1, midCol, count);
    fill(grid, x1, midRow, y1, midCol, count);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int[][] specialGrid(int n) {
    final int sz = 1 << n;
    int[][] grid = new int[sz][sz];
    fill(grid, 0, sz, 0, sz);
    return grid;
  }

  private int count = 0;

  private void fill(int[][] grid, int x1, int x2, int y1, int y2) {
    if (x2 - x1 == 1) {
      grid[x1][y1] = count++;
      return;
    }
    int midRow = (x1 + x2) / 2;
    int midCol = (y1 + y2) / 2;
    fill(grid, x1, midRow, midCol, y2);
    fill(grid, midRow, x2, midCol, y2);
    fill(grid, midRow, x2, y1, midCol);
    fill(grid, x1, midRow, y1, midCol);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def specialGrid(self, n: int) -> list[list[int]]:
    sz = 1 << n
    grid = [[0] * sz for _ in range(sz)]
    count = 0

    def fill(x1: int, x2: int, y1: int, y2: int) -> None:
      nonlocal count
      if x2 - x1 == 1:
        grid[x1][y1] = count
        count += 1
        return
      midRow = (x1 + x2) // 2
      midCol = (y1 + y2) // 2
      fill(x1, midRow, midCol, y2)
      fill(midRow, x2, midCol, y2)
      fill(midRow, x2, y1, midCol)
      fill(x1, midRow, y1, midCol)

    fill(0, sz, 0, sz)
    return grid