# Construct 2D Grid Matching Graph Layout
**Difficulty:** HARD
[External](https://leetcode.com/problems/construct-2d-grid-matching-graph-layout)
Canonical: https://scaleengineer.com/dsa/problems/construct-2d-grid-matching-graph-layout
**Data structures:** Array, Hash Table, Matrix, Graph
---
## Problem
You are given a 2D integer array `edges` representing an **undirected** graph having `n` nodes, where `edges[i] = [ui, vi]` denotes an edge between nodes `ui` and `vi`.

Construct a 2D grid that satisfies these conditions:

* The grid contains **all nodes** from `0` to `n - 1` in its cells, with each node appearing exactly **once**.
* Two nodes should be in adjacent grid cells (**horizontally** or **vertically**) **if and only if** there is an edge between them in `edges`.

It is guaranteed that `edges` can form a 2D grid that satisfies the conditions.

Return a 2D integer array satisfying the conditions above. If there are multiple solutions, return _any_ of them.

**Example 1:**

**Input:** n = 4, edges = \[\[0,1\],\[0,2\],\[1,3\],\[2,3\]\]

**Output:** \[\[3,1\],\[2,0\]\]

**Explanation:**

![](https://assets.glich.co/dsa/construct-2d-grid-matching-graph-layout/image0.png)

**Example 2:**

**Input:** n = 5, edges = \[\[0,1\],\[1,3\],\[2,3\],\[2,4\]\]

**Output:** \[\[4,2,3,1,0\]\]

**Explanation:**

![](https://assets.glich.co/dsa/construct-2d-grid-matching-graph-layout/image1.png)

**Example 3:**

**Input:** n = 9, edges = \[\[0,1\],\[0,4\],\[0,5\],\[1,7\],\[2,3\],\[2,4\],\[2,5\],\[3,6\],\[4,6\],\[4,7\],\[6,8\],\[7,8\]\]

**Output:** \[\[8,6,3\],\[7,4,2\],\[1,0,5\]\]

**Explanation:**

![](https://assets.glich.co/dsa/construct-2d-grid-matching-graph-layout/image2.png)

**Constraints:**

* `2 <= n <= 5 * 104`
* `1 <= edges.length <= 105`
* `edges[i] = [ui, vi]`
* `0 <= ui < vi < n`
* All the edges are distinct.
* The input is generated such that `edges` can form a 2D grid that satisfies the conditions.

# Approaches
## Backtracking Search
A brute-force approach would involve exploring all possible ways to place the `n` nodes onto a grid. This can be formulated as a backtracking search problem. We would start by placing one node, then recursively try to place its neighbors in adjacent cells, and so on. At each step, if we make a placement that violates the given adjacency rules (e.g., placing two non-adjacent nodes next to each other, or two adjacent nodes far apart), we backtrack and try a different placement. This process continues until all nodes are placed correctly.
**Time:** O(k^N) in the worst case, where k is the branching factor. This is far too slow for the given constraints. · **Space:** O(N) for the recursion stack and storing the grid state, but can be much larger depending on implementation.
**Pros:** Conceptually simple as it mirrors a direct search for a solution.
**Cons:** Extremely high time complexity, likely exponential, making it infeasible for the given constraints.; Complex to implement correctly, with many edge cases and state management (the grid can grow dynamically).; Does not leverage the strong guarantee that a valid grid structure exists.
### Explanation
This method attempts to build the grid by trying every possible valid placement for each node. It's a classic search algorithm that explores the solution space until a valid grid that satisfies all conditions is found.

Here's a conceptual outline of the algorithm:

1.  **Initialization**: Start with an empty grid (or a map to store node coordinates) and a set of unplaced nodes (initially all nodes from `0` to `n-1`).
2.  **Recursive Function**: A function `backtrack(grid, placed_nodes)` is the core of this approach.
3.  **Base Case**: If `placed_nodes.size() == n`, all nodes have been placed. We perform a final check to ensure all adjacency constraints are met. If they are, we have found a solution. Return `true`.
4.  **Recursive Step**: 
    a. Select a node to place. A good heuristic is to pick an unplaced node that is a neighbor of an already placed node.
    b. Select an empty grid cell to place it in. This cell must be adjacent to the corresponding placed neighbor.
    c. For each valid (node, cell) pair:
        i. Place the node in the cell.
        ii. Check for immediate constraint violations. For example, the new node's other neighbors in the grid must match its neighbors in the input `edges`.
        iii. If no violations, recursively call `backtrack()`.
        iv. If the recursive call returns `true`, propagate `true` up.
        v. If not, backtrack: remove the node from the cell and try the next option.
5.  **Failure**: If all possibilities are exhausted without finding a solution, return `false`.

Due to its combinatorial nature, this approach is not practical for the problem's constraints (`n` up to 50,000) and is presented here for theoretical comparison.
### Algorithm
1.  Represent the graph using an adjacency list.
2.  Define a recursive backtracking function, say `solve(grid, placed_nodes)`.
3.  The base case for the recursion is when all `n` nodes have been placed in the `grid`. If the resulting grid is valid, a solution is found.
4.  In the recursive step, iterate through all empty cells in the grid that are adjacent to already placed nodes.
5.  For each such empty cell, try placing each unplaced node one by one.
6.  After placing a node, check if the placement is valid so far (i.e., it doesn't violate any adjacency constraints with its new neighbors).
7.  If the partial placement is valid, make a recursive call: `solve(new_grid, new_placed_nodes)`.
8.  If the recursive call returns `false` (meaning it led to a dead end), backtrack by un-placing the node and try the next available node or cell.
9.  The process starts by placing an arbitrary node (e.g., node 0) at an arbitrary position (e.g., the center of a sufficiently large grid) and then calling the backtracking function.

## Deterministic Construction from a Corner
A highly efficient approach is to deterministically construct the grid by leveraging its rigid structure. Since we are guaranteed that the edges form a valid grid, we can find a corner and establish a coordinate system (i.e., 'right' and 'down' directions). Once the orientation is fixed, the position of every other node is uniquely determined.

The algorithm starts by finding a corner node (one with the minimum degree, typically 2). Using its two neighbors, we define one as being to the 'right' and the other as 'down'. With this, we can trace out the entire first row. Then, using the first row as an anchor, we can construct the second row, and so on, until all nodes are placed. Each node's position is found by identifying it as the common neighbor of its already-placed 'above' and 'left' neighbors. This avoids any backtracking and builds the grid in a single pass.
**Time:** O(N + E), where N is the number of nodes and E is the number of edges. Building the adjacency list takes O(N+E), and constructing the grid involves visiting each node and its edges a constant number of times. · **Space:** O(N + E), where N is the number of nodes and E is the number of edges. This is for storing the adjacency list and the resulting grid.
**Pros:** Highly efficient with linear time complexity.; Deterministic, providing a direct construction of the grid without searching.; Robustly handles any valid grid configuration (1D or 2D) due to the problem's guarantees.
**Cons:** The implementation logic is more involved than a simple traversal, requiring careful handling of node relationships.; Relies heavily on the guarantee that the input forms a perfect grid.
### Explanation
This approach constructs the grid without any searching or backtracking, leading to a very efficient solution.

### Algorithm Steps:

1.  **Build Adjacency List**: Create a `Map<Integer, Set<Integer>>` from the `edges` array for O(1) average time complexity for neighbor checks.

2.  **Find a Corner**: Identify a corner of the grid by finding a node with the minimum degree. For an M x N grid (M, N > 1), corners have a degree of 2. For a 1 x N grid (N > 2), corners have a degree of 1. Let's call this `corner`.

3.  **Handle 1D Case**: If `corner` has degree 1, the grid is a line. We can build the `1 x n` grid by starting at the `corner` and traversing to its neighbor, then its neighbor's other neighbor, and so on.

4.  **Handle 2D Case**: If `corner` has degree 2, we proceed with 2D construction.
    *   **Orient**: Get the two neighbors of `corner`, say `n1` and `n2`. Arbitrarily assign one as the node to the right (`rightNode`) and the other as the node down (`downNode`). For example, `rightNode = n1`, `downNode = n2`.
    *   **Build First Row**: Construct the first row starting with `[corner, rightNode]`. To find the next node in the row, say after `curr`, we need its neighbor that isn't the `prev` node in the row and isn't the node below `curr`. This process is repeated until the end of the row is reached.
    *   **Build Other Rows**: Once the first row is built, subsequent rows are built upon the previous one. The node at `grid[i][j]` is the unique common neighbor of `grid[i-1][j]` (the node above) and `grid[i][j-1]` (the node to the left), excluding `grid[i-1][j-1]`.

### Java Code Snippet:
```java
class Solution {
    public int[][] constructGrid(int n, int[][] edges) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++) adj.put(i, new HashSet<>());
        int[] degree = new int[n];
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        int minDegree = n;
        int startNode = -1;
        for (int i = 0; i < n; i++) {
            if (degree[i] < minDegree) {
                minDegree = degree[i];
                startNode = i;
            }
        }

        if (minDegree == 1 && n > 2) { // 1xN grid
            int[][] grid1D = new int[1][n];
            int prev = -1;
            int curr = startNode;
            for (int i = 0; i < n; i++) {
                grid1D[0][i] = curr;
                for (int neighbor : adj.get(curr)) {
                    if (neighbor != prev) {
                        prev = curr;
                        curr = neighbor;
                        break;
                    }
                }
            }
            return grid1D;
        }

        // 2D Grid Construction
        int corner = startNode;
        List<Integer> neighbors = new ArrayList<>(adj.get(corner));
        int rightNode = neighbors.get(0);
        int downNode = neighbors.get(1);

        // Build first row
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(corner);
        firstRow.add(rightNode);

        int pRowNode = corner;
        int cRowNode = rightNode;
        int pDownNode = downNode;

        while (adj.get(cRowNode).size() > 2) {
            int cDownNode = -1;
            for (int neighbor : adj.get(cRowNode)) {
                if (adj.get(pDownNode).contains(neighbor) && neighbor != pRowNode) {
                    cDownNode = neighbor;
                    break;
                }
            }
            int cRightNode = -1;
            for (int neighbor : adj.get(cRowNode)) {
                if (neighbor != pRowNode && neighbor != cDownNode) {
                    cRightNode = neighbor;
                    break;
                }
            }
            if (cRightNode == -1) break;
            firstRow.add(cRightNode);
            pRowNode = cRowNode;
            cRowNode = cRightNode;
            pDownNode = cDownNode;
        }

        List<List<Integer>> gridList = new ArrayList<>();
        gridList.add(firstRow);
        int numCols = firstRow.size();

        while (gridList.size() * numCols < n) {
            List<Integer> prevRow = gridList.get(gridList.size() - 1);
            List<Integer> currentRow = new ArrayList<>();
            int prevRowHead = prevRow.get(0);
            int currRowHead = -1;
            for (int neighbor : adj.get(prevRowHead)) {
                boolean isRight = prevRow.size() > 1 && neighbor == prevRow.get(1);
                boolean isUp = gridList.size() > 1 && neighbor == gridList.get(gridList.size() - 2).get(0);
                if (!isRight && !isUp) {
                    currRowHead = neighbor;
                    break;
                }
            }
            currentRow.add(currRowHead);

            for (int j = 1; j < numCols; j++) {
                int nodeAbove = prevRow.get(j);
                int nodeLeft = currentRow.get(j - 1);
                int nodeAboveLeft = prevRow.get(j - 1);
                for (int neighbor : adj.get(nodeAbove)) {
                    if (neighbor != nodeAboveLeft && adj.get(nodeLeft).contains(neighbor)) {
                        currentRow.add(neighbor);
                        break;
                    }
                }
            }
            gridList.add(currentRow);
        }

        int[][] result = new int[gridList.size()][numCols];
        for (int i = 0; i < gridList.size(); i++) {
            for (int j = 0; j < numCols; j++) {
                result[i][j] = gridList.get(i).get(j);
            }
        }
        return result;
    }
}
```
### Algorithm
1.  **Preprocessing**: Build an adjacency list, preferably using hash sets for efficient neighbor lookups (`Map<Integer, Set<Integer>>`). Also, compute the degree of each node.
2.  **Find a Starting Point**: Find the node with the minimum degree. If the minimum degree is 1, the graph is a 1D line. If it's 2, it's a 2D grid. This node will be a corner of the grid.
3.  **Handle 1D Grid**: If the minimum degree is 1, start from that node and perform a simple traversal, following the path of nodes to construct the single row (or column).
4.  **Handle 2D Grid (Orient the Corner)**: If the minimum degree is 2, let the starting node be `corner`. It has two neighbors, `n1` and `n2`. We must establish a `right` and `down` direction. We can arbitrarily assign `rightNode = n1` and `downNode = n2`. Since any valid grid is acceptable, this choice will lead to a correct solution.
5.  **Construct the First Row**: 
    a. Start the row with `[corner, rightNode]`.
    b. Iteratively find the next node in the row. Given the `previous` and `current` nodes in the row, the `next` node is the neighbor of `current` that is neither `previous` nor the node 'below' `current`. The node 'below' `current` can be identified as the common neighbor of `current` and the node 'below' `previous`.
    c. Continue until the end of the row is reached (a node with degree 2 or 3 on the edge).
6.  **Construct Subsequent Rows**: 
    a. Add the completed first row to your result grid.
    b. For each subsequent row, start by finding the head of the row, which is the 'down' neighbor of the head of the previous row.
    c. Fill the rest of the row. The node at `grid[i][j]` is determined by its neighbors at `grid[i-1][j]` (above) and `grid[i][j-1]` (left). It is their unique common neighbor that is not `grid[i-1][j-1]` (above-left).
7.  **Finalize**: Convert the list of lists into a 2D integer array and return it.

# Solutions
### Java

```java
class Solution {
public
  int[][] constructGridLayout(int n, int[][] edges) {
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int[] e : edges) {
      int u = e[0], v = e[1];
      g[u].add(v);
      g[v].add(u);
    }
    int[] deg = new int[5];
    Arrays.fill(deg, -1);
    for (int x = 0; x < n; x++) {
      deg[g[x].size()] = x;
    }
    List<Integer> row = new ArrayList<>();
    if (deg[1] != -1) {
      row.add(deg[1]);
    } else if (deg[4] == -1) {
      int x = deg[2];
      for (int y : g[x]) {
        if (g[y].size() == 2) {
          row.add(x);
          row.add(y);
          break;
        }
      }
    } else {
      int x = deg[2];
      row.add(x);
      int pre = x;
      x = g[x].get(0);
      while (g[x].size() > 2) {
        row.add(x);
        for (int y : g[x]) {
          if (y != pre && g[y].size() < 4) {
            pre = x;
            x = y;
            break;
          }
        }
      }
      row.add(x);
    }
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>(row));
    boolean[] vis = new boolean[n];
    int rowSize = row.size();
    for (int i = 0; i < n / rowSize - 1; i++) {
      for (int x : row) {
        vis[x] = true;
      }
      List<Integer> nxt = new ArrayList<>();
      for (int x : row) {
        for (int y : g[x]) {
          if (!vis[y]) {
            nxt.add(y);
            break;
          }
        }
      }
      res.add(new ArrayList<>(nxt));
      row = nxt;
    }
    int[][] ans = new int[res.size()][rowSize];
    for (int i = 0; i < res.size(); i++) {
      for (int j = 0; j < rowSize; j++) {
        ans[i][j] = res.get(i).get(j);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> constructGridLayout(int n, vector<vector<int>> &edges) {
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      g[u].push_back(v);
      g[v].push_back(u);
    }
    vector<int> deg(5, -1);
    for (int x = 0; x < n; ++x) {
      deg[g[x].size()] = x;
    }
    vector<int> row;
    if (deg[1] != -1) {
      row.push_back(deg[1]);
    } else if (deg[4] == -1) {
      int x = deg[2];
      for (int y : g[x]) {
        if (g[y].size() == 2) {
          row.push_back(x);
          row.push_back(y);
          break;
        }
      }
    } else {
      int x = deg[2];
      row.push_back(x);
      int pre = x;
      x = g[x][0];
      while (g[x].size() > 2) {
        row.push_back(x);
        for (int y : g[x]) {
          if (y != pre && g[y].size() < 4) {
            pre = x;
            x = y;
            break;
          }
        }
      }
      row.push_back(x);
    }
    vector<vector<int>> ans;
    ans.push_back(row);
    vector<bool> vis(n, false);
    int rowSize = row.size();
    for (int i = 0; i < n / rowSize - 1; ++i) {
      for (int x : row) {
        vis[x] = true;
      }
      vector<int> nxt;
      for (int x : row) {
        for (int y : g[x]) {
          if (!vis[y]) {
            nxt.push_back(y);
            break;
          }
        }
      }
      ans.push_back(nxt);
      row = nxt;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]: g = [[] for _ in range(n)] for u, v in edges: g[u]. append(v) g[v]. append(u) deg = [- 1] * 5 for x, ys in enumerate(g): deg[len(ys)] = x if deg[1] != - 1: row = [deg[1]] elif deg[4] == - 1: x = deg[2] for y in g[x]: if len(g[y]) == 2: row = [x, y] break else: x = deg[2] row = [x] pre = x x = g[x][0] while len(g[x]) > 2: row . append(x) for y in g[x]: if y != pre and len(g[y]) < 4: pre = x x = y break row . append(x) ans = [row] vis = [False] * n for _ in range(n // len(row) - 1): for x in row: vis[x] = True nxt = [] for x in row: for y in g[x]: if not vis[y]: nxt . append(y) break ans . append(nxt) row = nxt return ans

```