3311. Construct 2D Grid Matching Graph Layout

HardGraphArrayHash TableMatrix

Problem Description

You have an undirected graph with n nodes (numbered from 0 to n-1) and a list of edges connecting these nodes. Your task is to arrange all these nodes into a 2D grid layout that follows specific rules.

The input edges is a 2D array where each edges[i] = [ui, vi] represents an undirected edge between nodes ui and vi.

You need to construct a 2D grid where:

Every node from 0 to n-1 appears exactly once in the grid
Two nodes should be placed in adjacent cells (either horizontally or vertically adjacent) if and only if there's an edge between them in the original graph

The problem guarantees that such a valid 2D grid arrangement exists for the given edges.

For example, if you have nodes connected in a way that forms a grid pattern, you need to reconstruct that grid. Nodes that are connected by an edge must be neighbors in the grid (sharing a side), and nodes that aren't connected by an edge must not be neighbors in the grid.

The output should be a 2D array representing the grid layout with node numbers placed in their respective positions. If multiple valid arrangements exist, you can return any one of them.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that in a 2D grid, nodes have different degrees (number of connections) based on their position:

Corner nodes have degree 2 (connected to 2 neighbors)
Edge nodes (not corners) have degree 3 (connected to 3 neighbors)
Inner nodes have degree 4 (connected to 4 neighbors)
If the grid is just a single row or column, end nodes have degree 1 and middle nodes have degree 2

By analyzing the degree of each node, we can identify their positions in the grid and reconstruct it.

The solution starts by building the first row of the grid. There are three cases to consider:

Single node grid: If there's a node with degree 1, the grid is just a single row or column starting from this node.
Two-column grid: If no nodes have degree 4 (meaning no inner nodes exist), we have at most 2 columns. We find a node with degree 2 and one of its neighbors that also has degree 2 to form the first row.
Multi-row, multi-column grid: We identify a corner node (degree 2) and traverse along the edge to build the first row. We keep moving to adjacent nodes that have degree less than 4 (staying on the edge) until we reach another corner.

Once we have the first row, building the rest of the grid becomes straightforward. For each subsequent row:

Mark all nodes in the current row as visited
For each node in the current row, find its unvisited neighbor (which must be the node directly below it in the grid)
These neighbors form the next row

We repeat this process until all n nodes are placed. The number of rows is n / len(first_row).

This approach works because the grid structure ensures that each node in a row has exactly one unvisited neighbor that belongs to the next row (except for the last row), maintaining the proper adjacency relationships defined by the edges.

Learn more about Graph patterns.

Solution Approach

The implementation follows these steps:

Build the adjacency list: Create a graph g where g[i] contains all neighbors of node i.

g = [[] for _ in range(n)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

Categorize nodes by degree: Create an array deg where deg[d] stores a node with degree d. We only need degrees 1-4, so we initialize with size 5.

deg = [-1] * 5
for x, ys in enumerate(g):
    deg[len(ys)] = x

Build the first row based on three scenarios:

Case 1: Single row/column grid (deg[1] != -1):

If a node with degree 1 exists, start the row with this node

if deg[1] != -1:
    row = [deg[1]]

Case 2: Two-column grid (deg[4] == -1, no inner nodes):

Find a node with degree 2 and one of its neighbors that also has degree 2

elif deg[4] == -1:
    x = deg[2]
    for y in g[x]:
        if len(g[y]) == 2:
            row = [x, y]
            break

Case 3: Multi-row/column grid:

Start from a corner (degree 2 node)
Traverse along the edge by following neighbors with degree < 4
Stop when reaching another corner (degree 2)

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)

Build remaining rows:

Start with the first row in the answer grid
Use a visited array to track processed nodes
For each existing row, find the unvisited neighbor of each node (which forms the next row)

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

The algorithm efficiently reconstructs the grid in O(n) time by leveraging the degree information to identify node positions and using the adjacency relationships to build each row sequentially.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with 6 nodes forming a 2×3 grid:

Edges: [[0,1],[0,2],[1,3],[2,3],[2,4],[3,5],[4,5]]

Visual representation of the graph:
0 - 1
|   |
2 - 3
|   |
4 - 5

Step 1: Build adjacency list

g[0] = [1, 2]
g[1] = [0, 3]  
g[2] = [0, 3, 4]
g[3] = [1, 2, 5]
g[4] = [2, 5]
g[5] = [3, 4]

Step 2: Categorize nodes by degree

Nodes 0, 1, 4, 5 have degree 2 (corner nodes)
Nodes 2, 3 have degree 3 (edge nodes, not corners)
No nodes have degree 1 or 4

So deg = [-1, -1, 0, 2, -1] (storing one example node for each degree)

Step 3: Build first row Since deg[1] == -1 and deg[4] == -1, we're in Case 2 (two-column grid).

Start with node 0 (degree 2)
Check its neighbors: node 1 has degree 2, node 2 has degree 3
Choose node 1 as the second element
First row = [0, 1]

Step 4: Build remaining rows We need 3 rows total (6 nodes ÷ 2 columns = 3 rows).

Building row 2:

Mark nodes 0, 1 as visited
For node 0: unvisited neighbor is 2
For node 1: unvisited neighbor is 3
Second row = [2, 3]

Building row 3:

Mark nodes 2, 3 as visited (0, 1 already marked)
For node 2: unvisited neighbor is 4
For node 3: unvisited neighbor is 5
Third row = [4, 5]

Final Answer:

[[0, 1],
 [2, 3],
 [4, 5]]

This correctly places all nodes such that connected nodes are adjacent in the grid and unconnected nodes are not adjacent.

Solution Implementation

1class Solution:
2    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
3        # Build adjacency list representation of the graph
4        adjacency_list = [[] for _ in range(n)]
5        for u, v in edges:
6            adjacency_list[u].append(v)
7            adjacency_list[v].append(u)
8      
9        # Find a node with each degree (1 to 4)
10        # degree_to_node[i] stores a node with degree i, or -1 if no such node exists
11        degree_to_node = [-1] * 5
12        for node, neighbors in enumerate(adjacency_list):
13            degree_to_node[len(neighbors)] = node
14      
15        # Determine the first row of the grid based on node degrees
16        if degree_to_node[1] != -1:
17            # If there's a node with degree 1, it must be a 1xN or Nx1 grid
18            first_row = [degree_to_node[1]]
19        elif degree_to_node[4] == -1:
20            # No node with degree 4 means it's a 2xM grid
21            # Start with a corner node (degree 2)
22            corner_node = degree_to_node[2]
23            for neighbor in adjacency_list[corner_node]:
24                if len(adjacency_list[neighbor]) == 2:
25                    # Found the other corner node in the same row
26                    first_row = [corner_node, neighbor]
27                    break
28        else:
29            # There are nodes with degree 4, so we have a grid with more than 2 rows
30            # Start with a corner node (degree 2)
31            current_node = degree_to_node[2]
32            first_row = [current_node]
33            previous_node = current_node
34            current_node = adjacency_list[current_node][0]
35          
36            # Traverse along the first row until we reach another corner
37            while len(adjacency_list[current_node]) > 2:
38                first_row.append(current_node)
39                # Find the next node in the row (not the previous one and on the edge)
40                for neighbor in adjacency_list[current_node]:
41                    if neighbor != previous_node and len(adjacency_list[neighbor]) < 4:
42                        previous_node = current_node
43                        current_node = neighbor
44                        break
45            first_row.append(current_node)
46      
47        # Build the complete grid row by row
48        grid = [first_row]
49        visited = [False] * n
50        num_rows = n // len(first_row)
51      
52        # Generate remaining rows
53        for _ in range(num_rows - 1):
54            # Mark current row nodes as visited
55            for node in first_row:
56                visited[node] = True
57          
58            # Find the next row by getting unvisited neighbors
59            next_row = []
60            for node in first_row:
61                for neighbor in adjacency_list[node]:
62                    if not visited[neighbor]:
63                        next_row.append(neighbor)
64                        break
65          
66            grid.append(next_row)
67            first_row = next_row
68      
69        return grid
70

1class Solution {
2    public int[][] constructGridLayout(int n, int[][] edges) {
3        // Build adjacency list representation of the graph
4        List<Integer>[] adjacencyList = new List[n];
5        Arrays.setAll(adjacencyList, k -> new ArrayList<>());
6      
7        for (int[] edge : edges) {
8            int u = edge[0];
9            int v = edge[1];
10            adjacencyList[u].add(v);
11            adjacencyList[v].add(u);
12        }
13
14        // Store a node with degree i at degreeToNode[i]
15        // Initialize with -1 to indicate no node found
16        int[] degreeToNode = new int[5];
17        Arrays.fill(degreeToNode, -1);
18
19        // Map each degree to a representative node
20        for (int node = 0; node < n; node++) {
21            int degree = adjacencyList[node].size();
22            degreeToNode[degree] = node;
23        }
24
25        // Determine the first row of the grid
26        List<Integer> firstRow = new ArrayList<>();
27      
28        if (degreeToNode[1] != -1) {
29            // Case 1: Grid is 1xN (single row) - start with degree-1 node
30            firstRow.add(degreeToNode[1]);
31        } else if (degreeToNode[4] == -1) {
32            // Case 2: Grid is 2xM - no degree-4 nodes exist
33            // Start with a degree-2 node and its degree-2 neighbor
34            int startNode = degreeToNode[2];
35            for (int neighbor : adjacencyList[startNode]) {
36                if (adjacencyList[neighbor].size() == 2) {
37                    firstRow.add(startNode);
38                    firstRow.add(neighbor);
39                    break;
40                }
41            }
42        } else {
43            // Case 3: Grid has more than 2 rows
44            // Build first row by traversing from corner to corner
45            int currentNode = degreeToNode[2];  // Start from a corner (degree-2 node)
46            firstRow.add(currentNode);
47          
48            int previousNode = currentNode;
49            currentNode = adjacencyList[currentNode].get(0);  // Move to first neighbor
50          
51            // Traverse until we reach another corner
52            while (adjacencyList[currentNode].size() > 2) {
53                firstRow.add(currentNode);
54                // Find next node in the row (not the previous one, and on the edge)
55                for (int neighbor : adjacencyList[currentNode]) {
56                    if (neighbor != previousNode && adjacencyList[neighbor].size() < 4) {
57                        previousNode = currentNode;
58                        currentNode = neighbor;
59                        break;
60                    }
61                }
62            }
63            firstRow.add(currentNode);  // Add the final corner node
64        }
65
66        // Build the complete grid row by row
67        List<List<Integer>> grid = new ArrayList<>();
68        grid.add(new ArrayList<>(firstRow));
69
70        // Track visited nodes to avoid revisiting
71        boolean[] visited = new boolean[n];
72        int rowWidth = firstRow.size();
73        int numRows = n / rowWidth;
74      
75        // Build remaining rows
76        List<Integer> currentRow = firstRow;
77        for (int i = 0; i < numRows - 1; i++) {
78            // Mark current row nodes as visited
79            for (int node : currentRow) {
80                visited[node] = true;
81            }
82          
83            // Build next row by finding unvisited neighbors
84            List<Integer> nextRow = new ArrayList<>();
85            for (int node : currentRow) {
86                for (int neighbor : adjacencyList[node]) {
87                    if (!visited[neighbor]) {
88                        nextRow.add(neighbor);
89                        break;
90                    }
91                }
92            }
93          
94            grid.add(new ArrayList<>(nextRow));
95            currentRow = nextRow;
96        }
97
98        // Convert List<List<Integer>> to int[][]
99        int[][] result = new int[grid.size()][rowWidth];
100        for (int i = 0; i < grid.size(); i++) {
101            for (int j = 0; j < rowWidth; j++) {
102                result[i][j] = grid.get(i).get(j);
103            }
104        }
105      
106        return result;
107    }
108}
109

1class Solution {
2public:
3    vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {
4        // Build adjacency list representation of the graph
5        vector<vector<int>> graph(n);
6        for (auto& edge : edges) {
7            int u = edge[0], v = edge[1];
8            graph[u].push_back(v);
9            graph[v].push_back(u);
10        }
11
12        // Store a representative node for each degree (1 to 4)
13        // degreeNode[i] stores a node with degree i, or -1 if no such node exists
14        vector<int> degreeNode(5, -1);
15        for (int node = 0; node < n; ++node) {
16            degreeNode[graph[node].size()] = node;
17        }
18
19        // Build the first row of the grid
20        vector<int> firstRow;
21      
22        if (degreeNode[1] != -1) {
23            // Case 1: Single node graph (1x1 grid)
24            firstRow.push_back(degreeNode[1]);
25        } else if (degreeNode[4] == -1) {
26            // Case 2: No node with degree 4 exists (1x2 or 2xM grid)
27            int cornerNode = degreeNode[2];  // Start with a corner node (degree 2)
28          
29            // Find the adjacent node that also has degree 2
30            for (int neighbor : graph[cornerNode]) {
31                if (graph[neighbor].size() == 2) {
32                    firstRow.push_back(cornerNode);
33                    firstRow.push_back(neighbor);
34                    break;
35                }
36            }
37        } else {
38            // Case 3: Nodes with degree 4 exist (general MxN grid with M, N > 2)
39            int currentNode = degreeNode[2];  // Start with a corner node (degree 2)
40            firstRow.push_back(currentNode);
41          
42            int previousNode = currentNode;
43            currentNode = graph[currentNode][0];  // Move to first neighbor
44          
45            // Traverse the top edge until we reach another corner
46            while (graph[currentNode].size() > 2) {
47                firstRow.push_back(currentNode);
48              
49                // Find the next node along the edge (not going back)
50                for (int neighbor : graph[currentNode]) {
51                    if (neighbor != previousNode && graph[neighbor].size() < 4) {
52                        previousNode = currentNode;
53                        currentNode = neighbor;
54                        break;
55                    }
56                }
57            }
58            firstRow.push_back(currentNode);  // Add the final corner node
59        }
60
61        // Build the complete grid row by row
62        vector<vector<int>> grid;
63        grid.push_back(firstRow);
64      
65        vector<bool> visited(n, false);
66        int rowWidth = firstRow.size();
67        int numRows = n / rowWidth;
68      
69        // Generate remaining rows
70        for (int rowIndex = 0; rowIndex < numRows - 1; ++rowIndex) {
71            // Mark current row nodes as visited
72            for (int node : firstRow) {
73                visited[node] = true;
74            }
75          
76            // Find the next row by getting unvisited neighbors
77            vector<int> nextRow;
78            for (int node : firstRow) {
79                for (int neighbor : graph[node]) {
80                    if (!visited[neighbor]) {
81                        nextRow.push_back(neighbor);
82                        break;
83                    }
84                }
85            }
86          
87            grid.push_back(nextRow);
88            firstRow = nextRow;  // Update for next iteration
89        }
90
91        return grid;
92    }
93};
94

1/**
2 * Constructs a 2D grid layout from a graph with n nodes and given edges.
3 * The function identifies the grid structure based on node degrees and builds
4 * the grid row by row.
5 * 
6 * @param n - The number of nodes in the graph
7 * @param edges - Array of edges where each edge is [u, v] representing a connection
8 * @returns A 2D array representing the grid layout of nodes
9 */
10function constructGridLayout(n: number, edges: number[][]): number[][] {
11    // Build adjacency list representation of the graph
12    const adjacencyList: number[][] = Array.from({ length: n }, () => []);
13    for (const [u, v] of edges) {
14        adjacencyList[u].push(v);
15        adjacencyList[v].push(u);
16    }
17
18    // Map degree to a representative node with that degree
19    // degreeToNode[i] stores a node with degree i (or -1 if no such node exists)
20    const degreeToNode: number[] = Array(5).fill(-1);
21    for (let node = 0; node < n; node++) {
22        degreeToNode[adjacencyList[node].length] = node;
23    }
24
25    // Determine the first row of the grid based on node degrees
26    let currentRow: number[] = [];
27  
28    if (degreeToNode[1] !== -1) {
29        // Case 1: Grid is 1xN (single row) - start with degree-1 node
30        currentRow.push(degreeToNode[1]);
31    } else if (degreeToNode[4] === -1) {
32        // Case 2: Grid is 2xN - start with a degree-2 corner node
33        const cornerNode = degreeToNode[2];
34        for (const neighbor of adjacencyList[cornerNode]) {
35            if (adjacencyList[neighbor].length === 2) {
36                currentRow.push(cornerNode, neighbor);
37                break;
38            }
39        }
40    } else {
41        // Case 3: Grid is MxN where M,N > 2 - build first row from corner to corner
42        let currentNode = degreeToNode[2]; // Start with a corner node (degree 2)
43        currentRow.push(currentNode);
44      
45        let previousNode = currentNode;
46        currentNode = adjacencyList[currentNode][0]; // Move to first neighbor
47      
48        // Traverse the edge of the grid until we reach another corner
49        while (adjacencyList[currentNode].length > 2) {
50            currentRow.push(currentNode);
51            // Find the next node along the edge (not the previous one, and on the edge)
52            for (const neighbor of adjacencyList[currentNode]) {
53                if (neighbor !== previousNode && adjacencyList[neighbor].length < 4) {
54                    previousNode = currentNode;
55                    currentNode = neighbor;
56                    break;
57                }
58            }
59        }
60        currentRow.push(currentNode); // Add the final corner node
61    }
62
63    // Initialize the result grid with the first row
64    const resultGrid: number[][] = [currentRow];
65    const visited: boolean[] = Array(n).fill(false);
66    const rowLength = currentRow.length;
67
68    // Build remaining rows by finding unvisited neighbors of the current row
69    for (let rowIndex = 0; rowIndex < Math.floor(n / rowLength) - 1; rowIndex++) {
70        // Mark all nodes in the current row as visited
71        for (const node of currentRow) {
72            visited[node] = true;
73        }
74      
75        // Find the next row by getting unvisited neighbors of current row nodes
76        const nextRow: number[] = [];
77        for (const node of currentRow) {
78            for (const neighbor of adjacencyList[node]) {
79                if (!visited[neighbor]) {
80                    nextRow.push(neighbor);
81                    break;
82                }
83            }
84        }
85      
86        resultGrid.push(nextRow);
87        currentRow = nextRow;
88    }
89
90    return resultGrid;
91}
92

Time and Space Complexity

Time Complexity: O(n + m) where n is the number of nodes and m is the number of edges.

Building the adjacency list g takes O(m) time as we iterate through all edges once.
Computing the degree array takes O(n) time as we iterate through all nodes to count their degrees.
Finding the first row:
- In the simplest case (single node), it's O(1).
- In the case where we need to find a neighbor with degree 2, it's O(deg(x)) which is bounded by O(n).
- In the most complex case where we traverse to find the row, we visit at most O(n) nodes, and for each node, we check at most 4 neighbors (since max degree is 4), giving us O(n).
Building the answer grid:
- The outer loop runs O(n/cols) times where cols is the number of columns.
- In each iteration, we mark nodes as visited (O(cols)) and find the next row by checking neighbors (O(cols)).
- Total: O(n/cols × cols) = O(n).
Overall, the time complexity is O(m + n), which simplifies to O(n + m).

Space Complexity: O(n + m)

The adjacency list g stores all edges, requiring O(m) space (each edge is stored twice in an undirected graph).
The deg array is constant size O(1).
The row array stores at most O(n) elements.
The vis array stores n boolean values, requiring O(n) space.
The ans array stores all n nodes in a 2D structure, requiring O(n) space.
Total space complexity is O(n + m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Edge Case Handling for 2-Column Grids

A critical pitfall occurs when building the first row for a 2-column grid (when degree_to_node[4] == -1). The code assumes that finding any neighbor with degree 2 is sufficient, but this can lead to selecting two nodes that aren't actually in the same row.

Problem Example: Consider a 2×3 grid:

0 - 1
|   |
2 - 3
|   |
4 - 5

Node 0 (degree 2) has neighbor 2 (also degree 2), but they're in the same column, not row! This would create an invalid first row [0, 2].

Solution: Verify that the selected pair actually forms a valid row by checking if they share common neighbors:

elif degree_to_node[4] == -1:
    corner_node = degree_to_node[2]
    for neighbor in adjacency_list[corner_node]:
        if len(adjacency_list[neighbor]) == 2:
            # Additional validation: ensure they form a row
            # Two corner nodes in the same row won't share neighbors
            common_neighbors = set(adjacency_list[corner_node]) & set(adjacency_list[neighbor])
            if len(common_neighbors) == 0:
                first_row = [corner_node, neighbor]
                break

2. Missing Validation for Single Node Case

The code doesn't handle n = 1 properly. With a single node and no edges, the adjacency list construction works, but the degree array might not behave as expected.

Solution: Add an early return for the single node case:

def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
    if n == 1:
        return [[0]]
  
    # Rest of the code...

3. Assumption About Grid Orientation

The code assumes it's building rows, but for a 1×N grid (single column), the logic still creates a "row" with one element and tries to build multiple rows. While this technically works, it can be confusing and inefficient.

Solution: Explicitly handle the single row/column case to return immediately:

if degree_to_node[1] != -1:
    # Build the entire 1D chain at once
    current = degree_to_node[1]
    path = [current]
    visited = {current}
  
    while len(path) < n:
        for neighbor in adjacency_list[current]:
            if neighbor not in visited:
                path.append(neighbor)
                visited.add(neighbor)
                current = neighbor
                break
  
    # Return as either a single row or single column
    # Both are valid; choosing single row for consistency
    return [path]

4. Inefficient Neighbor Search in Row Building

When building subsequent rows, the code searches for unvisited neighbors without breaking the inner loop after finding one, potentially continuing unnecessary iterations.

Solution: While the current code does include a break, ensure it's properly indented and consider using a flag for clarity:

next_row = []
for node in first_row:
    found = False
    for neighbor in adjacency_list[node]:
        if not visited[neighbor]:
            next_row.append(neighbor)
            found = True
            break
    if not found and len(next_row) != len(first_row):
        # Handle error: expected to find an unvisited neighbor
        pass

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know