Construct 2d grid matching graph layout

impl Solution {
  pub fn construct_grid_layout(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = n as usize;
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }

    // Sort neighbour lists once; binary search gives O(log d) ≈ O(1) for d ≤ 4
    // and is faster than HashSet for these tiny lists (no heap allocation, better cache).
    for nbrs in adj.iter_mut() {
      nbrs.sort_unstable();
    }
    let degrees: Vec<usize> = (0..n).map(|i| adj[i].len()).collect();

    // O(1) adjacency test via binary search on a max-4-element sorted list.
    let is_adj = |u: usize, v: usize| adj[u].binary_search(&v).is_ok();

    // ── Determine grid dimensions ────────────────────────────────────────────
    // Corner nodes: degree 2 (or 1 for 1-row grid)
    // Edge nodes  : degree 3
    // Interior    : degree 4
    let min_deg = *degrees.iter().min().unwrap();
    let corners: Vec<usize> = (0..n).filter(|&i| degrees[i] == min_deg).collect();

    let (rows, cols) = if min_deg == 1 {
      (1, n)
    } else {
      // perimeter nodes with degree 3: count = 2*(rows+cols) - 8
      let cnt3 = degrees.iter().filter(|&&d| d == 3).count();
      let sum = (cnt3 + 8) / 2; // rows + cols
      let disc = sum * sum - 4 * n;
      let sqrt_disc = (disc as f64).sqrt() as usize;
      let r = (sum - sqrt_disc) / 2;
      (r, sum - r)
    };

    // ── Build first row ──────────────────────────────────────────────────────
    // Reusable flat bool array for O(1) row-membership — no HashSet allocation.
    let mut in_row = vec![false; n];

    // try_row: walk `cols` nodes along the row direction starting at
    // start_corner → first_nb, using col_dir as the initial "below" reference.
    let start_corner = corners[0];

    let try_row = |first_nb: usize, col_dir: usize, in_row: &mut Vec<bool>| -> Option<Vec<usize>> {
      if cols == 1 { return Some(vec![start_corner]); }
      let mut row = vec![start_corner, first_nb];
      in_row[start_corner] = true;
      in_row[first_nb] = true;

      if row.len() < cols {
        let mut prev = start_corner;
        let mut cur = first_nb;
        let mut down_prev = col_dir;
        while row.len() < cols {
          // Stay in the row: pick a neighbour of `cur` that is neither
          // `prev` nor adjacent to `down_prev` (which would go down).
          let next = adj[cur].iter()
            .find(|&&nb| nb != prev && !is_adj(nb, down_prev))
            .or_else(|| adj[cur].iter().find(|&&nb| nb != prev));
          match next {
            None => break,
            Some(&nb) => {
              let new_dp = adj[cur].iter().find(|&&x| x != prev && x != nb);
              in_row[nb] = true;
              row.push(nb);
              prev = cur;
              cur = nb;
              match new_dp {
                Some(&dp) => down_prev = dp,
                None => break,
              }
            }
          }
        }
      }

      // Validate: every interior node must have at least one neighbour not in
      // this row (i.e. the node below it). Uses in_row[] — no extra allocation.
      let valid = row.len() == cols && {
        rows == 1 || (1..cols - 1).all(|j| adj[row[j]].iter().any(|&nb| !in_row[nb]))
      };

      for &node in &row { in_row[node] = false; } // reset for next call / reuse
      if valid { Some(row) } else { None }
    };

    let first_row: Vec<usize> = if rows == 1 {
      // 1×n chain: just follow the path from the degree-1 corner.
      let mut row = vec![start_corner];
      let mut prev = n; // sentinel — out of bounds
      let mut cur = start_corner;
      while row.len() < cols {
        match adj[cur].iter().find(|&&nb| nb != prev) {
          None => break,
          Some(&nb) => { row.push(nb); prev = cur; cur = nb; }
        }
      }
      row
    } else {
      let na = adj[start_corner][0];
      let nb = adj[start_corner][1];
      try_row(na, nb, &mut in_row)
        .or_else(|| try_row(nb, na, &mut in_row))
        .unwrap_or_else(|| vec![start_corner])
    };

    // ── Fill subsequent rows ─────────────────────────────────────────────────
    // Single flat bool array tracks every node already placed in the grid.
    // For row k, each node above[j] (in row k-1) has exactly one neighbour
    // not yet in in_placed — that neighbour belongs to row k.
    // This eliminates all per-row HashSet/clone allocations.
    let mut in_placed = vec![false; n];
    for &node in &first_row { in_placed[node] = true; }

    let mut grid: Vec<Vec<usize>> = vec![first_row];

    for _ in 1..rows {
      let prev_row = grid.last().unwrap();
      let mut new_row = vec![0usize; cols];
      for j in 0..cols {
        // adj[above] has at most 4 entries — this is O(1) in practice.
        new_row[j] = *adj[prev_row[j]].iter().find(|&&nb| !in_placed[nb]).unwrap();
      }
      for &node in &new_row { in_placed[node] = true; }
      grid.push(new_row);
    }

    grid.into_iter().map(|row| row.into_iter().map(|x| x as i32).collect()).collect()
  }
}