3311. Construct 2D Grid Matching Graph Layout

HardGraphArrayHash TableMatrix

Problem Description

You are given a 2D integer array edges representing an undirected graph having n nodes, where edges[i] = [u_i, v_i] denotes an edge between nodes u_i and v_i.

You need to 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.

Intuition

To solve this problem, we need to construct a grid layout from the given edges that represents an undirected graph. The grid should contain all nodes exactly once and should maintain adjacency only where edges exist.

The solution approach involves:

Graph Representation: Create an adjacency list g to represent the graph. For each edge (u, v) in edges, update the adjacency list to reflect the bidirectional nature of the edge.
Degree Consideration: Determine the degrees of nodes and identify specific structures of the grid. Nodes with different degrees contribute to different grid positions. For instance:
- Nodes with a degree of 1 can help identify boundary nodes.
- Nodes with a degree of 2 or 3 often are in the middle or at the edge.
Row Construction: Start constructing the grid by building initial rows or columns based on the degrees of nodes:
- If a degree-2 node exists and no degree-4 nodes, identify a path using degree-2 nodes.
- Use degree-4 nodes to expand outward if needed.
Grid Expansion: After forming an initial row, expand the grid row by row. For each node in the current row, check its adjacent unvisited nodes to build the next row.

The basic steps involve identifying a starting point with a unique degree and progressively adding nodes in a manner maintaining connectivity and adjacency as per the graph's edges. Each expansion phase ensures that no nodes are revisited or left out, resulting in a complete grid satisfying the initial problem conditions.

Learn more about Graph patterns.

Solution Approach

The solution involves building a grid based on the nodes' connectivity using the following steps:

Graph Construction:

Initialize an adjacency list g where each node has a list of its neighbors. Iterate through each edge (u, v), adding v to u's neighbor list and vice versa.

g = [[] for _ in range(n)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

Identify Key Nodes by Degree:
- Create an array deg to categorize nodes based on their degree. This helps in identifying nodes that can start rows or columns in the grid layout.
- Update deg to record which nodes have specific degrees, focusing on nodes with unique roles like having a single connection or being part of a sequence.
```
deg = [-1] * 5
for x, ys in enumerate(g):
    deg[len(ys)] = x
```

Initial Row Construction:

Depending on the existence of degree-1 nodes or absence of degree-4 nodes, start constructing the initial row:
- If a degree-1 node exists, begin the row there.
- Without degree-4 nodes, look for a degree-2 node and its consecutive connections.
Otherwise, start building with degree-2 nodes, extending while encountering nodes with fewer than 4 connections.

if deg[1] != -1:
    row = [deg[1]]
elif deg[4] == -1:
    x = deg[2]
    for y in g[x]:
        if len(g[y]) == 2:
            row = [x, y]
            break

Grid Expansion:

Begin with the initial row, using ans to store the grid. Visits are tracked with vis.
For each row, determine the next row by finding unvisited neighbors for each node in the current row.

ans = [row]
vis = [False] * n
for _ in range(n // len(row) - 1):
    for x in row:
        vis[x] = True
    nxt = []
    for x in row:
        for y in g[x]:
            if not vis[y]:
                nxt.append(y)
                break
    ans.append(nxt)
    row = nxt

This algorithm efficiently constructs a valid grid based on the constraints defined, ensuring that both adjacency and inclusion conditions are met. The use of degree classification and adjacency list operations are key to dynamically building the grid structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Input

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

Creating the Graph

Graph Representation: We start by constructing an adjacency list g.

g = [[] for _ in range(n)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

After processing the edges, the adjacency list g looks like:

g = [
  [1, 3],    # Node 0 is connected to nodes 1 and 3
  [0, 2, 3], # Node 1 is connected to nodes 0, 2, and 3
  [1, 3],    # Node 2 is connected to nodes 1 and 3
  [2, 0, 1]  # Node 3 is connected to nodes 2, 0, and 1
]

Identify Key Nodes by Degree: Determine the nodes based on their connectivity (degree).

deg = [-1] * 5
for x, ys in enumerate(g):
    deg[len(ys)] = x

We find:

Nodes with degree 2: deg[2] is 0 or 2.
Node with degree 3: deg[3] is 1 or 3.

Initial Row Construction: Start forming the grid.

We select a starting node. Since there are no degree-1 nodes, we consider degree-2 nodes:

x = deg[2]  # Selecting one degree-2 node; for instance, start with node 0
row = [x]   # Initializing row with node 0

Node 0 connects to nodes 1 and 3, and we can select any node to begin the path; for example, let's pick node 1.
Continuing, we build the initial row [0, 1, 2, 3].

Grid Expansion: Construct the full grid.
- We start with the row [0, 1, 2, 3].
- This initial row already includes all nodes and satisfies adjacency constraints since nodes appear in the order of the edges.
Return the Grid: The complete grid could look like this:
```
ans = [
  [0, 1],
  [3, 2]
]
```
Each node appears once in the grid, and all nodes connected by edges are adjacent either horizontally or vertically. This forms a valid 2x2 grid based on the input edges.

This example demonstrates the process of transforming a graph described by edges into a grid that maintains the adjacency based on given conditions, effectively utilizing the algorithm specified in the solution approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
5        # Initialize adjacency list for graph with n nodes
6        graph = [[] for _ in range(n)]
7      
8        # Build the graph by adding edges to adjacency list
9        for u, v in edges:
10            graph[u].append(v)
11            graph[v].append(u)
12      
13        # Initialize a degree array to identify specific node patterns
14        degree_node = [-1] * 5
15
16        # Store the node with each degree (1, 2, etc.) if present
17        for node, neighbors in enumerate(graph):
18            degree_node[len(neighbors)] = node
19      
20        # Determine the starting row based on node degrees
21        if degree_node[1] != -1:
22            # If there's a node with degree 1, start with it
23            row = [degree_node[1]]
24        elif degree_node[4] == -1:
25            # If no node with degree 4, find two connected nodes with degree 2
26            x = degree_node[2]
27            for y in graph[x]:
28                if len(graph[y]) == 2:
29                    row = [x, y]
30                    break
31        else:
32            # Otherwise, create a row with a chain of nodes starting with a degree 2 node
33            x = degree_node[2]
34            row = [x]
35            pre = x
36            x = graph[x][0]
37          
38            # Traverse nodes and form a row until the node has more than 2 connections
39            while len(graph[x]) > 2:
40                row.append(x)
41                for y in graph[x]:
42                    if y != pre and len(graph[y]) < 4:
43                        pre = x
44                        x = y
45                        break
46            row.append(x)
47
48        # Initialize the result grid layout
49        grid_layout = [row]
50        visited = [False] * n
51      
52        # Construct the rest of the grid layout
53        for _ in range(n // len(row) - 1):
54            # Mark the current row nodes as visited
55            for x in row:
56                visited[x] = True
57          
58            # Find the next row of nodes, which are unvisited neighbors
59            next_row = []
60            for x in row:
61                for y in graph[x]:
62                    if not visited[y]:
63                        next_row.append(y)
64                        break
65            grid_layout.append(next_row)
66            row = next_row
67      
68        return grid_layout
69

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public int[][] constructGridLayout(int n, int[][] edges) {
7        // Create a graph with adjacency lists
8        List<Integer>[] graph = new List[n];
9        Arrays.setAll(graph, i -> new ArrayList<>());
10        // Fill the graph with the given edges
11        for (int[] edge : edges) {
12            int u = edge[0], v = edge[1];
13            graph[u].add(v);
14            graph[v].add(u);
15        }
16
17        // Array to store a node for each degree from 0 to 4
18        int[] degreeNodes = new int[5];
19        Arrays.fill(degreeNodes, -1);
20
21        // Determine the nodes corresponding to each degree
22        for (int i = 0; i < n; i++) {
23            degreeNodes[graph[i].size()] = i;
24        }
25
26        // List to hold the row of nodes in the layout
27        List<Integer> row = new ArrayList<>();
28        // Select a starting node
29        if (degreeNodes[1] != -1) {
30            row.add(degreeNodes[1]);  // Add if there's a node with degree 1
31        } else if (degreeNodes[4] == -1) {
32            int x = degreeNodes[2];
33            // Handling the case with degree 2
34            for (int neighbor : graph[x]) {
35                if (graph[neighbor].size() == 2) {
36                    row.add(x);
37                    row.add(neighbor);
38                    break;
39                }
40            }
41        } else {
42            // Handling the case with a full grid (degree 4)
43            int x = degreeNodes[2];
44            row.add(x);
45            int previous = x;
46            x = graph[x].get(0);
47            // Traverse the graph to build the row
48            while (graph[x].size() > 2) {
49                row.add(x);
50                for (int neighbor : graph[x]) {
51                    if (neighbor != previous && graph[neighbor].size() < 4) {
52                        previous = x;
53                        x = neighbor;
54                        break;
55                    }
56                }
57            }
58            row.add(x);
59        }
60
61        // Initialize the result list
62        List<List<Integer>> result = new ArrayList<>();
63        result.add(new ArrayList<>(row));
64
65        // Visited array
66        boolean[] visited = new boolean[n];
67        int rowSize = row.size();
68      
69        // Build the remaining rows
70        for (int i = 0; i < n / rowSize - 1; i++) {
71            // Mark nodes in the current row as visited
72            for (int x : row) {
73                visited[x] = true;
74            }
75            List<Integer> nextRow = new ArrayList<>();
76            // Build the next row from unvisited neighbors
77            for (int x : row) {
78                for (int neighbor : graph[x]) {
79                    if (!visited[neighbor]) {
80                        nextRow.add(neighbor);
81                        break;
82                    }
83                }
84            }
85            result.add(new ArrayList<>(nextRow));
86            row = nextRow;
87        }
88
89        // Convert the result list to a 2D array
90        int[][] gridLayout = new int[result.size()][rowSize];
91        for (int i = 0; i < result.size(); i++) {
92            for (int j = 0; j < rowSize; j++) {
93                gridLayout[i][j] = result.get(i).get(j);
94            }
95        }
96        return gridLayout;
97    }
98}
99

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {
7        // Create adjacency list for the given number of nodes and edges
8        vector<vector<int>> graph(n);
9        for (auto& edge : edges) {
10            int u = edge[0], v = edge[1];
11            graph[u].push_back(v);
12            graph[v].push_back(u);
13        }
14
15        // Initialize a vector to track nodes with a specific degree (0 to 4)
16        vector<int> nodeWithDegree(5, -1);
17        for (int node = 0; node < n; ++node) {
18            nodeWithDegree[graph[node].size()] = node;
19        }
20
21        // Initialize a row to store a sequence of nodes
22        vector<int> row;
23      
24        // Determine the starting point based on node degrees
25        if (nodeWithDegree[1] != -1) {
26            // If a node with degree 1 is present, start with it
27            row.push_back(nodeWithDegree[1]);
28        } else if (nodeWithDegree[4] == -1) {
29            // If no node with degree 4 exists, find a suitable path starting with a degree 2 node
30            int node = nodeWithDegree[2];
31            for (int neighbor : graph[node]) {
32                if (graph[neighbor].size() == 2) {
33                    row.push_back(node);
34                    row.push_back(neighbor);
35                    break;
36                }
37            }
38        } else {
39            // Otherwise, form a path including intermediate nodes
40            int node = nodeWithDegree[2];
41            row.push_back(node);
42            int previous = node;
43            node = graph[node][0];
44            while (graph[node].size() > 2) {
45                row.push_back(node);
46                for (int neighbor : graph[node]) {
47                    if (neighbor != previous && graph[neighbor].size() < 4) {
48                        previous = node;
49                        node = neighbor;
50                        break;
51                    }
52                }
53            }
54            row.push_back(node);
55        }
56
57        // Initialize the result grid layout
58        vector<vector<int>> result;
59        result.push_back(row);
60        vector<bool> visited(n, false);
61        int rowSize = row.size();
62
63        // Populate the grid by iterating over the nodes
64        for (int i = 0; i < n / rowSize - 1; ++i) {
65            // Mark current row nodes as visited
66            for (int node : row) {
67                visited[node] = true;
68            }
69
70            // Prepare the next row
71            vector<int> nextRow;
72            for (int node : row) {
73                for (int neighbor : graph[node]) {
74                    if (!visited[neighbor]) {
75                        nextRow.push_back(neighbor);
76                        break;
77                    }
78                }
79            }
80            result.push_back(nextRow);
81            row = nextRow;
82        }
83
84        // Return the constructed grid layout
85        return result;
86    }
87};
88

1// Constructs a grid layout based on given nodes and edges.
2function constructGridLayout(n: number, edges: number[][]): number[][] {
3    // Initialize an adjacency list to store the graph representation.
4    const graph: number[][] = Array.from({ length: n }, () => []);
5  
6    // Populate the adjacency list with edges, representing an undirected graph.
7    for (const [u, v] of edges) {
8        graph[u].push(v);
9        graph[v].push(u);
10    }
11
12    // Array to store the first node found with a specific degree (0 to 4).
13    const degreeNode: number[] = Array(5).fill(-1);
14    for (let x = 0; x < n; x++) {
15        degreeNode[graph[x].length] = x;
16    }
17
18    let row: number[] = [];
19  
20    // Check if there's a node with degree 1 and start the row with it.
21    if (degreeNode[1] !== -1) {
22        row.push(degreeNode[1]);
23    }
24    // If no node with degree 4 exists, create the row with nodes of degree 2.
25    else if (degreeNode[4] === -1) {
26        let x = degreeNode[2];
27        for (const y of graph[x]) {
28            if (graph[y].length === 2) {
29                row.push(x, y);
30                break;
31            }
32        }
33    }
34    // Otherwise, start constructing the row considering vertices with degree 2 and above.
35    else {
36        let x = degreeNode[2];
37        row.push(x);
38        let previous = x;
39        x = graph[x][0];
40        while (graph[x].length > 2) {
41            row.push(x);
42            for (const y of graph[x]) {
43                if (y !== previous && graph[y].length < 4) {
44                    previous = x;
45                    x = y;
46                    break;
47                }
48            }
49        }
50        row.push(x);
51    }
52
53    const result: number[][] = [row];
54    const visited: boolean[] = Array(n).fill(false);
55    const rowSize = row.length;
56
57    // Iterate through the grid to build subsequent rows.
58    for (let i = 0; i < Math.floor(n / rowSize) - 1; i++) {
59        for (const x of row) {
60            visited[x] = true;
61        }
62        const nextRow: number[] = [];
63        for (const x of row) {
64            for (const y of graph[x]) {
65                if (!visited[y]) {
66                    nextRow.push(y);
67                    break;
68                }
69            }
70        }
71        result.push(nextRow);
72        row = nextRow;
73    }
74
75    return result;
76}
77

Time and Space Complexity

The time complexity of the given code is O(n + m), where n is the number of nodes and m is the number of edges. This is because the code iterates over all nodes and edges to build the graph adjacency list g and then processes each node's neighbors to construct the grid layout.

The space complexity of the code is O(n + m) as well. The adjacency list g uses O(n + m) space to store the graph, and other auxiliary data structures like deg, row, and vis use additional O(n) space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know