LeetCode Solutions Blog

Construct 2D Grid Matching Graph Layout

Number: 3578

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an undirected graph with n nodes (labeled 0 to n-1) and a list of distinct edges, you are guaranteed that the graph is isomorphic to a 2D grid. That is, there is some way to place each node into a grid cell (each node exactly once) so that two nodes lie in adjacent grid cells (neighbors horizontally or vertically) if and only if there is an edge between them. The task is to return one valid 2D grid layout (as a 2D integer array) that satisfies these conditions.

Key Insights

Since the grid layout is “forced” by the isomorphic structure, the degrees of nodes give important clues. In any grid (with more than one row and column) the four corners have exactly 2 neighbors, the edge (but not corner) cells have 3, and inner cells have 4.
The number of nodes n must factor into two integers, say R and C, such that n = R * C. Moreover the number of edges in a grid equals (R-1)*C + (C-1)*R, so one can deduce R + C = 2n - |edges|.
A natural approach is to first compute the grid dimensions (R and C) using the relation above.
Then, one identifies a “corner” candidate (a node with degree 2 if R, C > 1, or degree 1 otherwise) and “seed” the grid by placing it into the top‐left cell.
Next, by “fixing” the two neighbors of the chosen corner to be (0,1) and (1,0) respectively, you can then fill the grid in row‐major order. When filling cell (r, c), use the already assigned adjacent cells – particularly the cell above (if any) and to the left (if any) – to determine the unique candidate for that position (namely, the unique node in the graph which is adjacent to both these already placed nodes and hasn’t been used yet).
The guarantee that the original graph can be “laid out” as a 2D grid assures that this procedure is well defined and that each cell gets exactly one node.

Space and Time Complexity

Time Complexity: O(n + m) where m equals the number of edges. The BFS/DFS procedure along with the neighbor intersections uses linear time relative to the number of nodes and edges. Space Complexity: O(n + m) as we store the graph as an adjacency list, maintain a mapping from nodes to their grid coordinates, and use an auxiliary grid of size R x C.

Solution

We solve the problem in several steps. First, deduce the grid dimensions by noticing that for a grid with R rows and C columns (n = R * C) the number of edges must equal (R-1)*C + (C-1)*R, which rearranges to R + C = 2n - m. Using this relation and trying all factor pairs of n, we can determine the unique valid (R, C).

Next, we represent the graph as an adjacency list. Then, we select a “corner” candidate – a node of degree 2 (or degree 1 in the degenerate one‐row/column case). We assign this node to grid cell (0,0) (our top‐left corner). Given a corner, the two adjacent positions in the grid are (0,1) and (1,0); the two neighbors of the corner are forced to go in those positions (the order may be arbitrary up to rotation/reflection, so any assignment that is consistent works).

With the first row and the first column “seeded”, we fill in the rest of the grid row by row. For each new cell (r, c) (with r, c not both 0) the already filled neighbor(s) (cell above at (r-1, c) and to the left at (r, c-1)) impose constraints: the candidate placed at (r, c) must be adjacent to both. Because the graph is exactly a grid, there will be exactly one unused node satisfying these adjacencies. We assign that node to (r, c) and continue until the grid is complete.

Throughout the procedure we use a mapping from node → (row, column) and a separate 2D array for the grid cells. The adjacency list (often implemented as a dictionary or vector of vectors) lets us quickly check if two nodes are connected.

It is important to note that while there might be several valid starting corner choices or neighbor assignment orders, any valid grid that meets the conditions is acceptable.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments. (Remember: do not use backticks; we use placeholder tags.)

# Python solution for constructing the 2D grid layout
from collections import deque, defaultdict
import math

def constructGrid(n, edges):
    # Build adjacency list for the graph
    graph = defaultdict(set)
    for u, v in edges:
        graph[u].add(v)
        graph[v].add(u)
    
    m = len(edges)
    # Determine grid dimensions (R, C) given n and m
    # We have: m = (R-1)*C + (C-1)*R = 2*n - (R + C)
    # So, R + C = 2*n - m
    sumRC = 2 * n - m
    R = C = None
    # Look for factor pair (r, c) such that r * c == n and r + c == sumRC
    for r in range(1, int(math.sqrt(n)) + 1):
        if n % r == 0:
            c = n // r
            if r + c == sumRC:
                R, C = r, c
                break
    # If not found, it might be a one-dimensional grid.
    if R is None:
        # For one-row (or one-column) grid, choose the obvious dimensions.
        if sumRC - 1 == n:
            R, C = 1, n
        else:
            R, C = n, 1

    # Initialize grid with -1 (indicating empty cells)
    grid = [[-1 for _ in range(C)] for _ in range(R)]
    # visited array to mark assigned nodes and dict to store node->(i,j)
    coord = {}
    
    # Choose a corner candidate:
    # In a grid with at least 2 rows and 2 cols, a corner node has 2 neighbors.
    corner_candidate = None
    for node in range(n):
        if (R == 1 or C == 1 and len(graph[node]) == 1) or (R > 1 and C > 1 and len(graph[node]) == 2):
            corner_candidate = node
            break
    if corner_candidate is None:
        # fallback: choose any node
        corner_candidate = 0

    # Place the corner candidate at grid[0][0]
    grid[0][0] = corner_candidate
    coord[corner_candidate] = (0,0)
    used = set([corner_candidate])
    
    # From corner, assign its two neighbors arbitrarily to the right and down,
    # if they exist. For 1-row or 1-column grid, only one direction applies.
    neighs = list(graph[corner_candidate])
    # helper function to attempt assignment in a given direction if possible
    def assign_neighbor_if_possible(from_node, pos):
        for neigh in graph[from_node]:
            if neigh not in used:
                grid[pos[0]][pos[1]] = neigh
                coord[neigh] = pos
                used.add(neigh)
                return True
        return False

    # For multi-row and multi-col grids we must assign two directions.
    if R > 1 and C > 1:
        # assign one neighbor to (0,1) and one to (1,0) if available
        if len(neighs) >= 2:
            grid[0][1] = neighs[0]
            coord[neighs[0]] = (0,1)
            used.add(neighs[0])
            grid[1][0] = neighs[1]
            coord[neighs[1]] = (1,0)
            used.add(neighs[1])
    elif R == 1:
        # one row: assign neighbor to the right (to fill row left-to-right)
        if neighs:
            grid[0][1] = neighs[0]
            coord[neighs[0]] = (0,1)
            used.add(neighs[0])
    elif C == 1:
        # one column: assign neighbor downwards
        if neighs:
            grid[1][0] = neighs[0]
            coord[neighs[0]] = (1,0)
            used.add(neighs[0])
    
    # Now fill the grid in row-major order.
    # The idea is: for each cell (i,j) that is still empty, use its already filled left and/or top neighbor 
    # to narrow down the candidate. For instance, if cell (i, j-1) is filled with node A, then the node we fill
    # in (i, j) must be one of A's neighbors that is not used yet.
    for i in range(R):
        for j in range(C):
            if grid[i][j] != -1:
                continue  # already assigned
            possible = None
            candidates = None
            # If there is a cell to the left, use its neighbors as candidates.
            if j - 1 >= 0:
                left = grid[i][j-1]
                candidates = graph[left] - used
            # If there is a cell above, intersect with its neighbors.
            if i - 1 >= 0:
                top = grid[i-1][j]
                if candidates is None:
                    candidates = graph[top] - used
                else:
                    candidates = candidates.intersection(graph[top])
            # There should be exactly one candidate in a correct grid layout.
            if candidates and len(candidates) == 1:
                possible = candidates.pop()
            else:
                # In some cases (e.g. the first cell of a row), only one of left or top exists.
                if candidates and len(candidates) >= 1:
                    possible = candidates.pop()
                else:
                    # fallback: search among all unseen nodes (though this should not happen for a valid grid)
                    for node in range(n):
                        if node not in used:
                            possible = node
                            break
            grid[i][j] = possible
            coord[possible] = (i,j)
            used.add(possible)
    
    # The grid now represents one valid layout.
    return grid

# Example usage:
n1 = 4
edges1 = [[0,1],[0,2],[1,3],[2,3]]
print(constructGrid(n1, edges1))