We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct 2D Grid Matching Graph Layout

Difficulty: Hard

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

Key Insights

  • The problem involves constructing a grid layout based on the adjacency of nodes defined by edges.
  • Each node must appear exactly once in the grid.
  • The adjacency of nodes in the grid corresponds directly to the edges in the graph.
  • The solution involves finding a way to traverse the graph while maintaining the grid structure.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. This accounts for the graph traversal. Space Complexity: O(n + m) for storing the adjacency list representation of the graph.

Solution

The solution involves using a graph traversal technique, such as BFS or DFS, to traverse through the nodes while keeping track of the grid positions. The adjacency list representation of the graph is built from the edges, and the traversal ensures that nodes connected by edges are placed in adjacent grid cells. Specifically, we can use a queue for BFS or a stack for DFS to explore the nodes and assign them to grid cells based on their adjacency.

Code Solutions

from collections import defaultdict, deque

def construct_grid(n, edges):
    # Create adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Initialize the grid
    side_length = int(n**0.5) + 1
    grid = [[-1] * side_length for _ in range(side_length)]
    
    # BFS to fill the grid
    queue = deque([0])
    visited = set([0])
    direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, Down, Left, Up
    x, y = 0, 0

    while queue:
        node = queue.popleft()
        grid[x][y] = node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
        
        # Move to the next cell in the grid
        y += 1
        if y >= side_length:
            y = 0
            x += 1

    return [row[:y] for row in grid[:x+1]]  # Trim the grid to the filled area
← Back to All Questions