Well-Structured Graph Solution with Topological Sorting
Intuition\nWe need to build a matrix that satisfies two conditions:\n\n1. Numbers should follow specific row orders.\n2. Numbers should follow specific column o
# Intuition\nWe need to build a matrix that satisfies two conditions:\n\n1. Numbers should follow specific row orders.\n2. Numbers should follow specific column orders.\n\nTo do this, we first convert these conditions into graphs and then perform topological sorting to find the order of numbers. Finally, we use this order to fill the matrix.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Create Graphs: Convert row and column conditions into graphs to track dependencies.\n2. Topological Sorting: Use topological sorting to find the valid order of numbers for rows and columns.\n3. Build Matrix: Create a matrix and fill it based on the sorted numbers for rows and columns.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n * m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n * m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * @param {number} k\n * @param {number[][]} rowConditions\n * @param {number[][]} colConditions\n * @return {number[][]}\n */\nvar buildMatrix = function (k, rowConditions, colConditions) {\n  const { graph: graphRow, startingPoints: startingPointsRow, degree: degreeRow } = createGraph(rowConditions, k)\n  const { graph: graphCol, startingPoints: startingPointsCol, degree: degreeCol } = createGraph(colConditions, k)\n\n  const row = traverseGraph(startingPointsRow, degreeRow, graphRow)\n  const col = traverseGraph(startingPointsCol, degreeCol, graphCol)\n\n  if (row.length !== k || col.length !== k) return []\n\n  const matrix = createMatrix(k, 0)\n\n  return fillMatrix(matrix, row, col)\n}\n\nfunction createMatrix (n, valueToFill) {\n  return Array.from({ length: n }, () => new Array(n).fill(valueToFill))\n}\n\nfunction createGraph (rowConditions, k) {\n  const degree = new Array(k + 1).fill(0)\n  const graph = {}//value -> [to]\n  const startingPoints = new Set([])\n\n  for (let i = 1; i <= k; i++) {\n    startingPoints.add(i)\n  }\n\n  rowConditions.forEach(rowCondition => {\n    const [to, from] = rowCondition\n\n    if (!graph[from]) {\n      graph[from] = {}\n    }\n\n    if (!graph[from][to]) {\n      graph[from][to] = true\n      startingPoints.delete(to)\n      degree[to]++\n    }\n  })\n\n  return { graph, startingPoints: [...startingPoints], degree }\n}\n\nfunction fillMatrix (matrix, row, col) {\n  for (let i = matrix.length - 1; i >= 0; i--) {\n    for (let j = matrix[0].length - 1; j >= 0; j--) {\n      if (row[i] === col[j]) {\n        matrix[matrix.length - i - 1][matrix[0].length - j - 1] = row[i]\n      }\n    }\n  }\n\n  return matrix\n}\n\nfunction traverseGraph (start, degree, graph) {\n  const added = new Set([])\n  const result = []\n\n  const queue = [...start]\n\n  while (queue.length) {\n    const popped = queue.shift()\n\n    if (!added.has(popped)) {\n      result.push(popped)\n      added.add(popped)\n    }\n\n    const adjVertices = graph[popped]\n\n    if (adjVertices) {\n      for (let vertex in adjVertices) {\n        degree[vertex]--\n\n        if (degree[vertex] === 0) {\n          queue.push(Number(vertex))\n        }\n      }\n    }\n  }\n\n  return result\n}\n\n```
['Graph', 'Topological Sort', 'JavaScript']