Practice Construct 2D Grid Matching Graph Layout
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Arrange all n graph nodes, numbered 0 through n-1, in a rectangular grid with each node used exactly once. Two nodes must share a horizontal or vertical grid side exactly when their pair is an edge. Diagonal contact does not count. A valid rectangular layout is guaranteed; return any such layout, including a single row when appropriate. Approach: A degree-1 node identifies a one-row path, which can be walked directly. Otherwise the degree-2 nodes are corners. Run BFS from a corner A, choose a nearest other corner B (an adjacent corner along the boundary, not the opposite corner), and run BFS from B. Let w=distance(A,B)+1. Each vertex v belongs at row=(distance(A,v)+distance(B,v)-(w-1))/2 and column=distance(A,v)-row. These distances recover the grid up to rotation or reflection in O(n+edges.length) time and space. Worked example: The first output below has seven side-sharing pairs, exactly the seven input edges. The second graph is a path; [[0,2,1]] preserves both edges without inventing an edge between 0 and 1.
Source: Construct 2D Grid Matching Graph Layout on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 6, edges = [[0,1],[1,2],[3,4],[4,5],[0,3],[1,4],[2,5]]
[[0,1,2],[3,4,5]]
# Example 2
n = 3, edges = [[0,2],[1,2]]
[[0,2,1]]
Constraints
How to solve Construct 2D Grid Matching Graph Layout
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
In a grid graph, breadth-first distance from a corner equals Manhattan distance, so distances from two corners sharing a side pin down every node's row and column; degrees reveal which nodes are corners.
Why brute force is not enough
Placing nodes by backtracking explores a factorial search space, hopeless for up to 50,000 nodes and 100,000 edges.
Approach
- Build adjacency lists and degrees. If any node has degree 1 the layout is a single row: start there and repeatedly step to the unvisited neighbor. With n equal to 2 both nodes have degree 1 and the walk still works.
- Otherwise the degree-2 nodes are corners. Run breadth-first search from a corner A, recording distances.
- Pick a second corner B that is not the farthest corner from A, so A and B share a side of w = dist(A,B) + 1 cells, and run breadth-first search from B.
- Place each node v at row (dist(A,v) + dist(B,v) - (w - 1)) / 2 and column dist(A,v) - row. Both distances are Manhattan distances in the true grid, so the two equations give a unique cell; the grid has n / w rows.
- Fill a 2D array by these coordinates and return it; any rotation or reflection is accepted.
Walkthrough of Example 1
n = 6, edges = [[0,1],[1,2],[3,4],[4,5],[0,3],[1,4],[2,5]] → [[0,1,2],[3,4,5]]
- n is 6 with edges [[0,1],[1,2],[3,4],[4,5],[0,3],[1,4],[2,5]]. Nodes 0, 2, 3, 5 have degree 2 and nodes 1, 4 have degree 3, so the corners are 0, 2, 3, 5.
- Search from A = 0 gives distances 0:0, 1:1, 3:1, 2:2, 4:2, 5:3. The farthest corner is 5, so 2 or 3 may serve as B; choosing B = 2 orients the grid like the sample, with w = 3.
- Search from B = 2 gives distances 2:0, 1:1, 5:1, 0:2, 4:2, 3:3.
- Rows: node 0 gets (0 + 2 - 2) / 2 = 0, node 1 gets 0, node 2 gets 0, node 3 gets (1 + 3 - 2) / 2 = 1, node 4 gets (2 + 2 - 2) / 2 = 1, node 5 gets (3 + 1 - 2) / 2 = 1.
- Columns are dist(A,v) minus row: 0, 1, 2 for nodes 0, 1, 2 and for nodes 3, 4, 5, producing [[0,1,2],[3,4,5]], the expected output. Choosing B = 3 gives the transposed grid, also valid.
Time and space
Time O(n + E) · Space O(n + E). n nodes and E edges; two breadth-first searches and one placement pass are linear, and adjacency lists plus distance arrays are linear in size.
Interview pitfalls
- Picking the corner opposite A as B, which makes w wrong and the coordinates meaningless.
- Missing the single-row case, where endpoints have degree 1 and there are no degree-2 corners.
- Mishandling n equal to 4 as a cycle, where every node has degree 2 and any node is a corner.
- Recursive search on a 50,000 node path overflowing the stack.
- Rejecting a correct answer because it is a rotation of the sample output.
Follow-up questions interviewers ask
- How would you verify in linear time that a layout satisfies exactly the given edges?
- What if the grid wrapped around like a cylinder or torus?
- Could you recover the layout from one corner's search by peeling the first row greedily?
Further reading on the technique: Breadth-first search
Related LeetCode Problems
Practice more problems similar to Construct 2D Grid Matching Graph Layout.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.