Construct 2D Grid Matching Graph Layout solution and explanation
The 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
0ton - 1in 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:
Example 2:
Input: n = 5, edges = [[0,1],[1,3],[2,3],[2,4]]
Output: [[4,2,3,1,0]]
Explanation:
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:
Constraints:
2 <= n <= 5 * 1041 <= edges.length <= 105edges[i] = [ui, vi]0 <= ui < vi < n- All the edges are distinct.
- The input is generated such that
edgescan form a 2D grid that satisfies the conditions.
Approach overview
Problem Overview: You are given an undirected graph that represents a valid grid structure. The goal is to place every node into a 2D matrix so that graph edges match the four grid neighbors (up, down, left, right). The layout must reconstruct the original grid shape while preserving adjacency.
Approach 1: Degree-Based Row Construction + BFS Placement (O(V + E) time, O(V) space)
The key observation is that nodes in a grid have predictable degrees. Corners have degree 2, edge cells have degree 3, and internal cells have degree 4. Start by identifying a corner node (degree 2). From that corner, walk through neighbors that also belong to the boundary to construct the first row of the grid. Once the top row is fixed, run a BFS traversal from these nodes to fill the remaining rows. Maintain a visited set and adjacency list from the graph. Each BFS expansion places neighbors directly below their corresponding parent cell, ensuring adjacency matches the original edges. This approach works because the graph guarantees a valid grid layout, so every node has a deterministic position relative to previously placed nodes.
Approach 2: Coordinate Assignment with BFS Traversal (O(V + E) time, O(V) space)
Another practical approach assigns coordinates while performing a single BFS. Pick any corner node as the origin and give it coordinate (0,0). As you traverse neighbors, assign them adjacent coordinates such as (x+1,y), (x-1,y), (x,y+1), or (x,y-1). A hash map stores the coordinate of each node and prevents revisiting. Because the input graph forms a valid grid, coordinate conflicts will not occur. After BFS finishes, normalize the coordinates so the smallest row and column start at zero, then place nodes into a matrix. This technique treats the grid reconstruction as a coordinate labeling problem over a breadth-first search traversal.
Recommended for interviews: The BFS coordinate assignment approach is usually the cleanest explanation. It shows you understand graph traversal and spatial reconstruction. Mentioning node-degree properties demonstrates deeper insight about grid graphs, but BFS placement is typically what interviewers expect because it directly maps graph neighbors to grid coordinates in linear time.
Approach 1: Breadth-First Search (BFS) approach for grid layout
This approach uses Breadth-First Search (BFS) to map the graph into a 2D grid structure. We start by picking a boundary node (a node with a relatively smaller number of edges) and placing it in the grid. Then, we queue its neighbors and continue placing them in adjacent grid cells until the entire grid is constructed.
from collections import deque, defaultdict
def construct_grid(n, edges):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
# Start BFS from a boundary node
start_node = next(node for node in range(n) if len(adj[node]) < 4)
rows, cols = n, n
grid = [[-1] * cols for _ in range(rows)]
visited = set()
queue = deque([(start_node, 0, 0)])
grid[0][0] = start_node
visited.add(start_node)
while queue:
node, r, c = queue.popleft()
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
# next available cells for placing the node
if c + 1 < cols and grid[r][c + 1] == -1:
grid[r][c + 1] = neighbor
queue.append((neighbor, r, c + 1))
elif r + 1 < rows and grid[r + 1][c] == -1:
grid[r + 1][c] = neighbor
queue.append((neighbor, r + 1, c))
# Construct the required subgrid
result = [row for row in grid if any(x != -1 for x in row)]
return [list(filter(lambda x: x != -1, row)) for row in result]
# Example usage:
n = 4
edges = [[0,1],[0,2],[1,3],[2,3]]
print(construct_grid(n, edges))#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
vector<vector<int>> constructGrid(int n, vector<vector<int>>& edges) {
unordered_map<int, unordered_set<int>> adj;
for (auto& edge : edges) {
adj[edge[0]].insert(edge[1]);
adj[edge[1]].insert(edge[0]);
}
// Find a boundary node
int startNode = 0;
for (int i = 0; i < n; ++i) {
if (adj[i].size() < 4) {
startNode = i;
break;
}
}
const int rows = n, cols = n;
vector<vector<int>> grid(rows, vector<int>(cols, -1));
queue<tuple<int, int, int>> q;
unordered_set<int> visited;
visited.insert(startNode);
grid[0][0] = startNode;
q.push({startNode, 0, 0});
while (!q.empty()) {
auto [node, r, c] = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
if (c + 1 < cols && grid[r][c + 1] == -1) {
grid[r][c + 1] = neighbor;
q.push({neighbor, r, c + 1});
} else if (r + 1 < rows && grid[r + 1][c] == -1) {
grid[r + 1][c] = neighbor;
q.push({neighbor, r + 1, c});
}
}
}
}
// Construct the required subgrid
vector<vector<int>> result;
for (auto& row : grid) {
vector<int> actRow;
for (int x : row) {
if (x != -1) actRow.push_back(x);
}
if (!actRow.empty()) result.push_back(actRow);
}
return result;
}
// Example usage:
// int n = 4;
// vector<vector<int>> edges = {{0,1},{0,2},{1,3},{2,3}};
// auto grid = constructGrid(n, edges);function constructGrid(n, edges) {
const adj = new Map();
for (const [u, v] of edges) {
if (!adj.has(u)) adj.set(u, []);
if (!adj.has(v)) adj.set(v, []);
adj.get(u).push(v);
adj.get(v).push(u);
}
let startNode = -1;
for (let i = 0; i < n; i++) {
if ((adj.get(i) || []).length < 4) {
startNode = i;
break;
}
}
const maxSize = n;
const grid = Array.from({length: maxSize}, () => Array(maxSize).fill(-1));
const queue = [[startNode, 0, 0]];
grid[0][0] = startNode;
const visited = new Set([startNode]);
while (queue.length > 0) {
const [node, r, c] = queue.shift();
for (const neighbor of (adj.get(node) || [])) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
if (c + 1 < maxSize && grid[r][c + 1] === -1) {
grid[r][c + 1] = neighbor;
queue.push([neighbor, r, c + 1]);
} else if (r + 1 < maxSize && grid[r + 1][c] === -1) {
grid[r + 1][c] = neighbor;
queue.push([neighbor, r + 1, c]);
}
}
}
}
return grid.map(row => row.filter(x => x !== -1)).filter(row => row.length > 0);
}
// Example usage:
// const n = 4;
// const edges = [[0,1],[0,2],[1,3],[2,3]];
// console.log(constructGrid(n, edges));This Python code defines a function construct_grid that takes two arguments, n and edges. It constructs a 2D grid from the edges using BFS. The BFS starts from a node with fewer edges (a boundary node) and attempts to fill the grid with neighbors in adjacent cells.
Time Complexity: O(n) where n is the number of nodes. We traverse each node once.
Space Complexity: O(n), the space needed for the grid and BFS queue.
Approach 2: Default Approach
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;
}
}function constructGridLayout(n: number, edges: number[][]): number[][] {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const deg: number[] = Array(5).fill(-1);
for (let x = 0; x < n; x++) {
deg[g[x].length] = x;
}
let row: number[] = [];
if (deg[1] !== -1) {
row.push(deg[1]);
} else if (deg[4] === -1) {
let x = deg[2];
for (const y of g[x]) {
if (g[y].length === 2) {
row.push(x, y);
break;
}
}
} else {
let x = deg[2];
row.push(x);
let pre = x;
x = g[x][0];
while (g[x].length > 2) {
row.push(x);
for (const y of g[x]) {
if (y !== pre && g[y].length < 4) {
pre = x;
x = y;
break;
}
}
}
row.push(x);
}
const ans: number[][] = [row];
const vis: boolean[] = Array(n).fill(false);
const rowSize = row.length;
for (let i = 0; i < Math.floor(n / rowSize) - 1; i++) {
for (const x of row) {
vis[x] = true;
}
const nxt: number[] = [];
for (const x of row) {
for (const y of g[x]) {
if (!vis[y]) {
nxt.push(y);
break;
}
}
}
ans.push(nxt);
row = nxt;
}
return ans;
}func constructGridLayout(n int, edges [][]int) [][]int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
deg := make([]int, 5)
for i := range deg {
deg[i] = -1
}
for x := 0; x < n; x++ {
deg[len(g[x])] = x
}
var row []int
if deg[1] != -1 {
row = append(row, deg[1])
} else if deg[4] == -1 {
x := deg[2]
for _, y := range g[x] {
if len(g[y]) == 2 {
row = append(row, x, y)
break
}
}
} else {
x := deg[2]
row = append(row, x)
pre := x
x = g[x][0]
for len(g[x]) > 2 {
row = append(row, x)
for _, y := range g[x] {
if y != pre && len(g[y]) < 4 {
pre = x
x = y
break
}
}
}
row = append(row, x)
}
ans := [][]int{row}
vis := make([]bool, n)
rowSize := len(row)
for i := 0; i < n/rowSize-1; i++ {
for _, x := range row {
vis[x] = true
}
nxt := []int{}
for _, x := range row {
for _, y := range g[x] {
if !vis[y] {
nxt = append(nxt, y)
break
}
}
}
ans = append(ans, nxt)
row = nxt
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) approach for grid layout | Time Complexity: O(n) where n is the number of nodes. We traverse each node once. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Degree-Based Row Construction + BFS | O(V + E) | O(V) | When you want deterministic grid reconstruction using node degree properties |
| BFS Coordinate Assignment | O(V + E) | O(V) | General case; simplest implementation that maps neighbors to coordinates |
| Brute Force Placement with Adjacency Validation | O(V^2) | O(V) | Useful only for understanding the constraint; impractical for large graphs |
Frequently asked questions
Is Construct 2D Grid Matching Graph Layout easy or hard?
Construct 2D Grid Matching Graph Layout is classified as Hard because it combines graph traversal with spatial reconstruction. Recognizing grid degree patterns and mapping neighbors to coordinates requires careful reasoning. Once the BFS coordinate strategy is understood, the implementation becomes manageable.
Construct 2D Grid Matching Graph Layout Python/Java solution
Implement the algorithm by building an adjacency list, running BFS from a corner node, and assigning coordinates to neighbors as you traverse. Python typically uses deque and dictionaries, Java uses Queue and HashMap, and C++ uses queue with unordered_map. All implementations maintain O(V + E) time complexity.
How to solve Construct 2D Grid Matching Graph Layout in O(V+E)?
Build an adjacency list and run BFS starting from a corner node. Assign grid coordinates while visiting neighbors so each edge corresponds to one of the four directions. Store coordinates in a hash map and track visited nodes. After traversal, shift coordinates to positive indices and construct the final matrix.
What is the best approach for Construct 2D Grid Matching Graph Layout?
The most reliable solution uses Breadth-First Search (BFS) to assign coordinates to each node. Starting from a corner node, BFS explores neighbors and maps them to adjacent grid positions. Because the input graph represents a valid grid, this traversal reconstructs the layout without conflicts. The overall complexity is O(V + E) time with O(V) extra space.
Is Construct 2D Grid Matching Graph Layout asked at Google/Amazon/Meta?
Graph reconstruction and grid-embedding problems commonly appear in interviews at companies like Google, Amazon, and Meta. The question tests understanding of BFS traversal, graph adjacency, and mapping nodes to spatial coordinates. Variations may ask you to rebuild grids, matrices, or coordinate systems from graph relationships.
What data structure is used in Construct 2D Grid Matching Graph Layout?
The solution relies on an adjacency list for the graph, a queue for BFS traversal, and a hash map to store node-to-coordinate mappings. A visited set prevents revisiting nodes during traversal. The final result is stored in a 2D matrix representing the reconstructed grid.
What is the time complexity of Construct 2D Grid Matching Graph Layout?
The optimal solution runs in O(V + E) time where V is the number of nodes and E is the number of edges. BFS processes each node once and scans each adjacency list once. Additional work to normalize coordinates and build the matrix is linear in the number of nodes.