3311. Construct 2D Grid Matching Graph Layout LeetCode Solution

In this guide, you will get 3311. Construct 2D Grid Matching Graph Layout LeetCode Solution with the best time and space complexity. The solution to Construct D Grid Matching Graph Layout problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct D Grid Matching Graph Layout solution in C++
Construct D Grid Matching Graph Layout solution in Java
Construct D Grid Matching Graph Layout solution in Python
Additional Resources

3311. Construct 2D Grid Matching Graph Layout LeetCode Solution image

Problem Statement of Construct D Grid Matching Graph Layout

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3311. Construct 2D Grid Matching Graph Layout LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    // Randomly choose a node with the minimum degree as the corner.
    const int corner =
        ranges::min_element(graph, ranges::less{}, &vector<int>::size) -
        graph.begin();

    vector<bool> seen(n);
    seen[corner] = true;
    const vector<int> firstRow = getFirstRow(graph, corner, seen);
    const int cols = firstRow.size();
    const int rows = n / cols;

    vector<vector<int>> ans(rows, vector<int>(cols));
    ans[0] = firstRow;

    for (int i = 1; i < rows; ++i)
      for (int j = 0; j < cols; ++j)
        for (const int v : graph[ans[i - 1][j]])
          if (!seen[v]) {
            ans[i][j] = v;
            seen[v] = true;
            break;
          }

    return ans;
  }

 private:
  vector<int> getFirstRow(vector<vector<int>>& graph, int corner,
                          vector<bool>& seen) {
    const int cornerDegree = graph[corner].size();
    vector<int> row = {corner};

    // Continue appending neighbors until we hit another corner.
    while (row.size() == 1 || graph[row.back()].size() == cornerDegree + 1) {
      // Sort neighbors by degree to prioritize smaller ones (shortest row built
      // first).
      vector<int>& neighbors = graph[row.back()];
      ranges::sort(neighbors, ranges::less{},
                   [&graph](int v) { return graph[v].size(); });
      for (const int v : neighbors)
        if (!seen[v] && (graph[v].size() == cornerDegree ||
                         graph[v].size() == cornerDegree + 1)) {
          row.push_back(v);
          seen[v] = true;
          break;
        }
    }

    return row;
  }
};
/* code provided by PROGIEZ */

3311. Construct 2D Grid Matching Graph Layout LeetCode Solution in Java

class Solution {
  public int[][] constructGridLayout(int n, int[][] edges) {
    List<Integer>[] graph = new ArrayList[n];

    for (int i = 0; i < n; i++)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    // Randomly choose a node with the minimum degree as the corner.
    int corner = 0;
    for (int i = 1; i < n; i++)
      if (graph[i].size() < graph[corner].size())
        corner = i;

    boolean[] seen = new boolean[n];
    seen[corner] = true;
    int[] firstRow = getFirstRow(graph, corner, seen);
    int cols = firstRow.length;
    int rows = n / cols;

    int[][] ans = new int[rows][cols];
    ans[0] = firstRow;

    for (int i = 1; i < rows; ++i)
      for (int j = 0; j < cols; ++j)
        for (final int v : graph[ans[i - 1][j]])
          if (!seen[v]) {
            ans[i][j] = v;
            seen[v] = true;
            break;
          }

    return ans;
  }

  private int[] getFirstRow(List<Integer>[] graph, int corner, boolean[] seen) {
    final int cornerDegree = graph[corner].size();
    List<Integer> row = new ArrayList<>(List.of(corner));
    // Continue appending neighbors until we hit another corner.
    while (row.size() == 1 || graph[row.get(row.size() - 1)].size() == cornerDegree + 1) {
      List<Integer> neighbors = graph[row.get(row.size() - 1)];
      Collections.sort(neighbors, (a, b) -> graph[a].size() - graph[b].size());
      for (final int v : neighbors)
        if (!seen[v] && (graph[v].size() == cornerDegree || graph[v].size() == cornerDegree + 1)) {
          row.add(v);
          seen[v] = true;
          break;
        }
    }
    return row.stream().mapToInt(Integer::intValue).toArray();
  }
}
// code provided by PROGIEZ

3311. Construct 2D Grid Matching Graph Layout LeetCode Solution in Python

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)

    # Randomly choose a node with the minimum degree as the corner.
    corner = min(range(len(graph)), key=lambda x: len(graph[x]))

    seen = {corner}
    firstRow = self._getFirstRow(graph, corner, seen)
    cols = len(firstRow)
    rows = n // cols

    ans = [[0] * cols for _ in range(rows)]
    ans[0] = firstRow

    for i in range(1, rows):
      for j in range(cols):
        for v in graph[ans[i - 1][j]]:
          if v not in seen:
            ans[i][j] = v
            seen.add(v)
            break

    return ans

  def _getFirstRow(
      self,
      graph: list[list[int]],
      corner: int,
      seen: set[int]
  ) -> list[int]:
    cornerDegree = len(graph[corner])
    row = [corner]
    # Continue appending neighbors until we hit another corner.
    while len(row) == 1 or len(graph[row[-1]]) == cornerDegree + 1:
      # Sort neighbors by degree to prioritize smaller ones (shortest row built first).
      graph[row[-1]].sort(key=lambda x: len(graph[x]))
      for v in graph[row[-1]]:
        if v not in seen and len(graph[v]) in (cornerDegree, cornerDegree + 1):
          row.append(v)
          seen.add(v)
          break
    return row
 # code by PROGIEZ