Skip to content

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.

Hard#3311
LeetCode Problem

Construct 2D Grid Matching Graph Layout

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

Input
n = 6, edges = [[0,1],[1,2],[3,4],[4,5],[0,3],[1,4],[2,5]]
Output
[[0,1,2],[3,4,5]]

# Example 2

Input
n = 3, edges = [[0,2],[1,2]]
Output
[[0,2,1]]

Constraints

There are 2 to 50,000 nodes and 1 to 100,000 distinct edges.
Each edge contains integers u and v with 0 <= u < v < n.
The graph is guaranteed to admit the required rectangular layout.

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

  1. 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.
  2. Otherwise the degree-2 nodes are corners. Run breadth-first search from a corner A, recording distances.
  3. 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.
  4. 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.
  5. 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]]

  1. 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.
  2. 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.
  3. Search from B = 2 gives distances 2:0, 1:1, 5:1, 0:2, 4:2, 3:3.
  4. 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.
  5. 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.