Skip to main content
Talentd

Construct 2D Grid Matching Graph Layout - Solution & Explanation

HardArrayHash TableGraphMatrix11 min read
Practice this problem

Problem Statement

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 0 to n - 1 in 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 * 104
  • 1 <= edges.length <= 105
  • edges[i] = [ui, vi]
  • 0 <= ui < vi < n
  • All the edges are distinct.
  • The input is generated such that edges can 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.

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.

Code

PythonC++JavaScript

Python

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) approach for grid layout

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Degree-Based Row Construction + BFSO(V + E)O(V)When you want deterministic grid reconstruction using node degree properties
BFS Coordinate AssignmentO(V + E)O(V)General case; simplest implementation that maps neighbors to coordinates
Brute Force Placement with Adjacency ValidationO(V^2)O(V)Useful only for understanding the constraint; impractical for large graphs

Video Solution

Leetcode Weekly Contest 418 | 3311. Construct 2D Grid Matching Graph Layout | CodeFod • CodeFod • 842 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Construct 2D Grid Matching Graph Layout with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays