Skip to content

3311. Construct 2D Grid Matching Graph Layout 👍

  • Time: O(n)O(n)
  • Space: O(n)O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
Was this page helpful?