LeetCode 3311 - Construct 2D Grid Matching Graph Layout

LeetCode Problem 3311

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Graph Theory, Matrix

Solution

Problem Understanding

The problem gives us an undirected graph with n nodes labeled from 0 to n - 1. We must place every node into a 2D grid so that adjacency in the grid matches adjacency in the graph exactly.

Two cells are considered adjacent only if they share a side, meaning horizontal or vertical neighbors. Diagonal neighbors do not count.

The condition is bidirectional:

• If two nodes are connected by an edge in the graph, they must appear in adjacent grid cells.
• If two nodes are adjacent in the grid, there must be an edge between them in the graph.

This means the graph must behave exactly like the adjacency graph of a rectangular grid.

The input consists of:

• n, the number of nodes
• edges, a list of undirected edges

The output is any valid 2D arrangement of all nodes.

The constraints are large:

• Up to 5 * 10^4 nodes
• Up to 10^5 edges

Because of this, exponential search or brute-force placement is impossible. We need a near-linear solution.

The important guarantee is extremely valuable:

The input is guaranteed to form a valid 2D grid layout.

That means we never need to handle impossible cases.

There are several important structural observations:

• Corner cells in a grid have degree 2
• Edge cells have degree 3
• Interior cells have degree 4
• A single-row grid behaves differently, because endpoints have degree 1 and middle nodes have degree 2

These degree patterns allow us to reconstruct the grid structure.

Some edge cases that can easily break naive implementations include:

• A graph that forms only one row
• Very thin grids such as 2 x k
• Large rectangular grids
• Multiple valid layouts
• Traversal order accidentally producing duplicate placements

The key challenge is discovering the correct row structure from only graph connectivity.

Approaches

Brute Force Approach

A brute-force solution would try every possible arrangement of nodes into rectangular grids.

We could:

1. Enumerate all possible grid dimensions whose product is n
2. Try every permutation of nodes
3. Check whether grid adjacency matches graph adjacency

This works theoretically because we can verify correctness directly.

However, the complexity is catastrophic. Even trying all permutations alone requires O(n!) time, which is completely infeasible for n = 5 * 10^4.

Even smarter backtracking approaches would still explode combinatorially because each placement affects many adjacency constraints.

The brute-force method is useful only for understanding the problem definition, not for solving it efficiently.

Key Insight

A valid grid graph has strong structural properties.

The degree of each node immediately tells us what kind of cell it occupies:

• Degree 2, corner
• Degree 3, edge
• Degree 4, interior
• Degree 1, endpoint of a single-row grid

The most important insight is that the first row of the grid can be reconstructed uniquely using degree transitions.

Once we know one row, every subsequent row becomes determined automatically.

The algorithm works by:

1. Identifying a corner node
2. Walking across the first row using degree information
3. Building remaining rows by selecting unused neighbors

Because every node in a grid has very constrained adjacency relationships, reconstruction becomes deterministic.

This converts the problem from exponential search into graph traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Tries permutations of node placements
Optimal	O(n + m)	O(n + m)	Reconstructs grid using graph structure

Here, m = edges.length.

Algorithm Walkthrough

Step 1: Build the Graph

We first construct an adjacency list.

For every edge [u, v]:

• Add v to u's neighbor list
• Add u to v's neighbor list

We also compute each node's degree.

The adjacency list is necessary because we repeatedly need to explore neighboring nodes efficiently.

Step 2: Handle Single Row Grids

If the graph contains a node with degree 1, the grid must be a single row.

Why?

In a rectangular grid:

• Only a one-dimensional path graph contains degree-1 nodes
• A normal 2D rectangle has minimum degree 2

So if degree-1 nodes exist, we simply reconstruct the path.

We:

1. Start from one endpoint
2. Walk forward while avoiding the previous node
3. Collect nodes into one row

This produces the entire layout directly.

Step 3: Find a Corner Node

If no degree-1 nodes exist, the grid has at least two rows and two columns.

We pick any node with degree 2.

Such a node must be a corner.

This corner becomes the starting point of the first row.

Step 4: Construct the First Row

The hardest part is discovering how many columns the grid has.

Suppose the current node is on the top row.

Among its neighbors:

• One neighbor continues along the row
• Another neighbor goes downward

We need to identify the horizontal continuation.

The key observation is:

• Along the top row:

• Corners have degree 2

• Non-corner edge cells have degree 3

So we walk from the starting corner until we reach another corner.

More precisely:

1. Start with the corner node
2. Repeatedly choose an unvisited neighbor whose degree is less than 4
3. Continue until reaching another degree-2 node

This sequence becomes the first row.

Step 5: Build Remaining Rows

Once the first row is known, the number of columns is fixed.

Now we iteratively build lower rows.

For each node in the current row:

• Find an unused neighbor
• That unused neighbor must lie directly below it

Because the graph is guaranteed valid, this placement is always unique.

We repeat until all nodes are used.

Step 6: Return the Grid

The collected rows form the final answer.

Why it works

A valid grid graph has rigid local structure.

The first row forms a boundary path connecting two corners. Boundary nodes have degree less than 4, which allows us to trace the row uniquely.

Once the first row is fixed, every node below each column is determined because each grid position has only one unused vertical neighbor remaining.

Since the graph is guaranteed to represent a valid rectangular grid, this reconstruction always succeeds and places every node exactly once.

Python Solution

from typing import List
from collections import deque

class Solution:
    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        degree = [len(graph[i]) for i in range(n)]

        # Single row case
        endpoints = [i for i in range(n) if degree[i] == 1]

        if endpoints:
            start = endpoints[0]

            row = []
            prev = -1
            curr = start

            while curr != -1:
                row.append(curr)

                nxt = -1
                for nei in graph[curr]:
                    if nei != prev:
                        nxt = nei
                        break

                prev, curr = curr, nxt

            return [row]

        # Multi-row grid
        start = next(i for i in range(n) if degree[i] == 2)

        first_row = [start]
        used = {start}

        prev = -1
        curr = start

        while True:
            nxt = -1

            for nei in graph[curr]:
                if nei == prev or nei in used:
                    continue

                if degree[nei] < 4:
                    nxt = nei
                    break

            if nxt == -1:
                break

            first_row.append(nxt)
            used.add(nxt)

            prev, curr = curr, nxt

            if degree[curr] == 2:
                break

        cols = len(first_row)

        grid = [first_row]

        used = set(first_row)

        while len(used) < n:
            prev_row = grid[-1]
            new_row = []

            for node in prev_row:
                for nei in graph[node]:
                    if nei not in used:
                        new_row.append(nei)
                        used.add(nei)
                        break

            grid.append(new_row)

        return grid

The implementation starts by constructing the adjacency list representation of the graph.

The first major branch handles the special case where the graph is simply a path. Degree-1 nodes identify path endpoints, and traversal reconstructs the row directly.

For genuine 2D grids, the algorithm begins from a corner node, identified by degree 2.

The first row is reconstructed carefully. We continue along neighbors whose degree is less than 4 because top boundary nodes cannot be interior nodes.

After determining the first row width, the remaining rows are generated iteratively. Every node in a row contributes exactly one unused neighbor below it.

The used set guarantees that no node is placed twice.

Go Solution

package main

func constructGridLayout(n int, edges [][]int) [][]int {
	graph := make([][]int, n)

	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	degree := make([]int, n)
	for i := 0; i < n; i++ {
		degree[i] = len(graph[i])
	}

	// Single row case
	endpoints := []int{}

	for i := 0; i < n; i++ {
		if degree[i] == 1 {
			endpoints = append(endpoints, i)
		}
	}

	if len(endpoints) > 0 {
		start := endpoints[0]

		row := []int{}

		prev := -1
		curr := start

		for curr != -1 {
			row = append(row, curr)

			next := -1

			for _, nei := range graph[curr] {
				if nei != prev {
					next = nei
					break
				}
			}

			prev, curr = curr, next
		}

		return [][]int{row}
	}

	// Multi-row grid
	start := -1

	for i := 0; i < n; i++ {
		if degree[i] == 2 {
			start = i
			break
		}
	}

	firstRow := []int{start}

	used := make([]bool, n)
	used[start] = true

	prev := -1
	curr := start

	for {
		next := -1

		for _, nei := range graph[curr] {
			if nei == prev || used[nei] {
				continue
			}

			if degree[nei] < 4 {
				next = nei
				break
			}
		}

		if next == -1 {
			break
		}

		firstRow = append(firstRow, next)
		used[next] = true

		prev, curr = curr, next

		if degree[curr] == 2 {
			break
		}
	}

	grid := [][]int{firstRow}

	for lenCount(used) < n {
		prevRow := grid[len(grid)-1]
		newRow := []int{}

		for _, node := range prevRow {
			for _, nei := range graph[node] {
				if !used[nei] {
					newRow = append(newRow, nei)
					used[nei] = true
					break
				}
			}
		}

		grid = append(grid, newRow)
	}

	return grid
}

func lenCount(arr []bool) int {
	count := 0

	for _, v := range arr {
		if v {
			count++
		}
	}

	return count
}

The Go implementation follows the same logic as the Python solution.

A boolean slice is used instead of a hash set for tracking used nodes because Go slices provide efficient indexed access.

Unlike Python, Go does not have built-in sets, so []bool is the simplest efficient alternative.

The traversal logic remains identical.

Worked Examples

Example 1

Input:

n = 4
edges = [[0,1],[0,2],[1,3],[2,3]]

Graph degrees:

Node	Degree
0	2
1	2
2	2
3	2

Every node is a corner because this is a 2 x 2 grid.

Start from node 0.

First row construction:

Current	Candidate Boundary Neighbor	Row
0	1	[0,1]

We stop because node 1 also has degree 2.

First row becomes:

[0,1]

Now build second row.

Unused neighbors:

Above Node	Unused Neighbor
0	2
1	3

Second row:

[2,3]

Final grid:

[
  [0,1],
  [2,3]
]

Example 2

Input:

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

Degrees:

Node	Degree
0	1
1	2
2	2
3	2
4	1

Degree-1 nodes exist, so this is a single-row grid.

Path traversal:

Current	Next	Row
0	1	[0]
1	3	[0,1]
3	2	[0,1,3]
2	4	[0,1,3,2]
4	-	[0,1,3,2,4]

Final layout:

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

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]
]

Degrees:

Node	Degree
0	3
1	2
2	3
3	2
4	4
5	2
6	3
7	3
8	2

Start from corner node 1.

First row traversal:

Current	Next Boundary Node	Row
1	0	[1,0]
0	5	[1,0,5]

Node 5 has degree 2, so stop.

First row:

[1,0,5]

Second row:

Above	Unused Neighbor
1	7
0	4
5	2

Second row:

[7,4,2]

Third row:

Above	Unused Neighbor
7	8
4	6
2	3

Third row:

[8,6,3]

Final grid:

[
  [1,0,5],
  [7,4,2],
  [8,6,3]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Every node and edge is processed a constant number of times
Space	O(n + m)	Adjacency list plus bookkeeping structures

The adjacency list requires O(n + m) memory.

Every traversal step examines neighboring edges only a constant number of times, so total work remains linear in the graph size.

This is efficient enough for the maximum constraints.

Test Cases

from typing import List
from collections import deque

class Solution:
    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        degree = [len(graph[i]) for i in range(n)]

        endpoints = [i for i in range(n) if degree[i] == 1]

        if endpoints:
            start = endpoints[0]

            row = []
            prev = -1
            curr = start

            while curr != -1:
                row.append(curr)

                nxt = -1
                for nei in graph[curr]:
                    if nei != prev:
                        nxt = nei
                        break

                prev, curr = curr, nxt

            return [row]

        start = next(i for i in range(n) if degree[i] == 2)

        first_row = [start]
        used = {start}

        prev = -1
        curr = start

        while True:
            nxt = -1

            for nei in graph[curr]:
                if nei == prev or nei in used:
                    continue

                if len(graph[nei]) < 4:
                    nxt = nei
                    break

            if nxt == -1:
                break

            first_row.append(nxt)
            used.add(nxt)

            prev, curr = curr, nxt

            if len(graph[curr]) == 2:
                break

        grid = [first_row]

        used = set(first_row)

        while len(used) < n:
            prev_row = grid[-1]
            new_row = []

            for node in prev_row:
                for nei in graph[node]:
                    if nei not in used:
                        new_row.append(nei)
                        used.add(nei)
                        break

            grid.append(new_row)

        return grid

s = Solution()

# Example 1, 2x2 grid
ans = s.constructGridLayout(
    4,
    [[0,1],[0,2],[1,3],[2,3]]
)
assert len(ans) == 2  # verifies square grid reconstruction

# Example 2, single row path
assert s.constructGridLayout(
    5,
    [[0,1],[1,3],[2,3],[2,4]]
) == [[0,1,3,2,4]]  # verifies path handling

# Example 3, 3x3 grid
ans = s.constructGridLayout(
    9,
    [
        [0,1],[0,4],[0,5],
        [1,7],
        [2,3],[2,4],[2,5],
        [3,6],
        [4,6],[4,7],
        [6,8],[7,8]
    ]
)
assert len(ans) == 3  # verifies multi-row construction

# Minimal path graph
assert s.constructGridLayout(
    2,
    [[0,1]]
) == [[0,1]]  # smallest valid input

# 2x3 grid
ans = s.constructGridLayout(
    6,
    [
        [0,1],[1,2],
        [3,4],[4,5],
        [0,3],[1,4],[2,5]
    ]
)
assert len(ans) == 2  # verifies rectangular layout

# 3x2 grid
ans = s.constructGridLayout(
    6,
    [
        [0,1],[2,3],[4,5],
        [0,2],[2,4],
        [1,3],[3,5]
    ]
)
assert len(ans) == 3  # verifies tall grid

Test	Why
2x2 square	Verifies smallest non-trivial 2D grid
Single-row path	Verifies degree-1 special handling
3x3 grid	Verifies interior degree-4 logic
n = 2	Verifies minimal boundary case
2x3 rectangle	Verifies rectangular reconstruction
3x2 rectangle	Verifies non-square layouts

Edge Cases

Single Row Graph

A graph shaped like a simple path contains degree-1 endpoints. This case is fundamentally different from true 2D grids because there are no corner degree-2 nodes.

A buggy implementation might incorrectly try to build multiple rows and fail.

The solution handles this immediately by detecting degree-1 nodes and reconstructing the path directly.

Very Small Grids

The smallest possible input is n = 2.

In this case, both nodes have degree 1, and the entire graph is just a single edge.

Algorithms assuming at least one degree-2 corner would crash or loop incorrectly.

The explicit path-handling branch avoids this problem entirely.

Interior Nodes With Degree 4

In larger grids, interior nodes have degree 4 and should never appear on the boundary.

A naive traversal could accidentally enter the interior while constructing the first row.

The implementation prevents this by continuing the first-row traversal only through nodes whose degree is less than 4.

This guarantees the traversal stays on the outer boundary until reaching the opposite corner.