Fill a special grid

Array Divide and Conquer Matrix

70.7% acceptance

Feb 25, 2026

111

You are given a non-negative integer n representing a 2n x 2n grid. You must fill the grid with integers from 0 to 2^(2n) - 1 to make it special. A grid is special if: 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. Note: Any 1x1 grid is special.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn special_grid(n: i32) -> Vec<Vec<i32>> {
    let size = 1usize << n;
    let mut grid = vec![vec![0i32; size]; size];
    fill(&mut grid, 0, 0, size, 0);
    grid
  }
}

// Fill a `sz x sz` subgrid starting at (row, col) with values [start, start + sz*sz)
// Order: top-right=lowest, bottom-right, bottom-left, top-left=highest
fn fill(grid: &mut Vec<Vec<i32>>, row: usize, col: usize, sz: usize, start: i32) {
  if sz == 1 {
    grid[row][col] = start;
    return;
  }
  let half = sz / 2;
  let q = (half * half) as i32;
  // top-right quadrant: rows [row, row+half), cols [col+half, col+sz) -> lowest values
  fill(grid, row, col + half, half, start);
  // bottom-right quadrant
  fill(grid, row + half, col + half, half, start + q);
  // bottom-left quadrant
  fill(grid, row + half, col, half, start + 2 * q);
  // top-left quadrant: highest values
  fill(grid, row, col, half, start + 3 * q);
}