Beginner Friendly Solution with Graph and Topological Sort + Visualization (Step By Step) 😊😊
Intuition\nThe code aims to construct a matrix of size k x k based on two sets of conditions: rowConditions and colConditions. These conditions specify relation
# Intuition\nThe code aims to construct a matrix of size k x k based on two sets of conditions: rowConditions and colConditions. These conditions specify relationships between elements within rows and columns. The problem seems to involve finding a valid ordering of elements that satisfies these relationships, possibly using a topological sort algorithm.\n\n# Approach\n1. Build Graphs: Create directed graphs to represent the relationships specified by rowConditions and colConditions. Each node in the graph represents a row or column index, and an edge from node A to B indicates that element A should be placed above/left of element B in the final matrix.\n2. Topological Sort: Perform a topological sort on each graph to determine a valid ordering of rows and columns. If a cycle exists in either graph, it means the conditions are impossible to satisfy, and we return an empty matrix.\n3. Construct Matrix: Create an empty k x k matrix. Iterate through the sorted rows and columns, filling each cell with the corresponding element value.\n\n# Complexity\n- Time complexity: O(k\xB2 + m + n), where k is the size of the matrix, and m and n are the lengths of the rowConditions and colConditions arrays respectively.\n\n- Space complexity: O(k\xB2 + m + n), where k is the size of the matrix, and m and n are the lengths of the rowConditions and colConditions arrays respectively.\n\n# Visualization\n- rowConditions = [[1, 2],[3, 2]]\n- colConditions = [[2, 1],[3, 2]]\n\nCreate Row Conditions Graph and Row Indegree Table:\n```\n1    3   \n|   /   \n|  /\n* *  \n2 \n\n// 1 point to 2 and 3 point to 2\n// rowIndegree:\n1: 0\n2: 2\n3: 0\n```\n\nGet the row order using topological sort:\nWe start by initializing a stack and rowOrder array,\n- stack = []\n- rowOrder = []\n- rowIndegree:\n1: 0\n2: 2\n3: 0\n\nAfter that we fill the stack with the indegree value of zero, in this case we have 1 and 3 with indegree of zero,\nstack = [1, 3]\n\nWe do the topological sort using a while loop to check if there is any vertex/node in the stack, in this case there is 1 and 3 in the stack so we take the last item (since we use stack) so we pull out 3 and put it inside our rowOrder array,\n- stack = [1]\n- rowOrder = [3]\n\nThe next thing we need to do is to decrement the indegree value of the vertex/node we just pull out, in this case we pull out 3 and 3 point to 2, so we decrement 2 by 1.\n- rowIndegree:\n1: 0\n2: 1\n3: 0\n\nAfter that we pull out 1 since the stack is not empty and put it inside our rowOrder array,\n- stack = []\n- rowOrder = [3, 1]\n\nThe next thing we need to do is to decrement the indegree value of the vertex/node we just pull out, in this case we pull out 1 and 1 point to 1, so we decrement 2 by 1.\n- rowIndegree:\n1: 0\n2: 0\n3: 0\n\nSince the the indegree value of 2 is now 0, we can put it on our stack,\n- stack = [2]\n- rowOrder = [3, 1]\n\nAfter that we pull out 2 since the stack is not empty and put it inside our rowOrder array,\n- stack = []\n- rowOrder = [3, 1, 2]\n\nAfter that, our stack is finally empty and the last thing we need to check is whether or not the conditions can be satisfy. Meaning there is no cycle in our graph by check the length of the rowOrder and k value which in this case is equal, so no cycle.\n\nP.S. The thing that we do here is really similar with the thing that we need to do in "Course Schedule" question. (https://leetcode.com/problems/course-schedule/solutions/5510273/beginner-friendly-solution-with-graph-and-topological-sort/) - Check it out \uD83D\uDE0A\uD83D\uDE0A\n\nCreate Col Conditions Graph and Col Indegree Table:\n```\n2 *   \n|  \\  \n|   \\\n*    3\n1 \n\n// 3 point to 2 and 2 point to 1\n// colIndegree:\n1: 1\n2: 1\n3: 0\n```\nGet the col order using topological sort:\nThe step to get the order for the column is really similar with what we do for the row, so in the end we will have row order of,\n- colOrder = [3, 2, 1]\n\nInsert value to matrix:\nAfter we done with our topological sort we have all the order for the row and col for the specific value (1 to k). We just need to combine this by mapping in the row and col.\n- rowOrder = [3, 1, 2]\n- rowMap = { \'1\': 1, \'2\': 2, \'3\': 0 }\nvalue of \'1\' is in index of 1\nvalue of \'2\' is in index of 2\nvalue of \'3\' is in index of 0\n\n- colOrder = [3, 2, 1]\n- colMap = { \'1\': 2, \'2\': 1, \'3\': 0 }\nvalue of \'1\' is in index of 2\nvalue of \'2\' is in index of 1\nvalue of \'3\' is in index of 0\n\nFinally, we just need to insert it inside the matrix by the coressponding map value we have. Value \'3\' is inserted in [0,0], value \'2\' is inserted in [2,1], and value \'1\' is inserted in [1,2]:\n- [3, 0, 0]\n[0, 0, 1]\n[0, 2, 0]\n\nThat\'s it, hopefully you find this useful and try to run it yourself. Thanks. \uD83D\uDE0A\uD83D\uDE0A\n\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  // create rowConditions graph and rowIndegree\n  const rowGraph = new Array(k).fill(null).map(() => new Array());\n  const rowIndegree = new Array(k).fill(0);\n\n  for (let rowCondition of rowConditions) {\n    let [above, below] = rowCondition;\n    above = above - 1; // we need to minus 1 because our array is indexed from 0 to 2, but the conditions is 1 to 3.\n    below = below - 1;\n    rowGraph[above].push(below);\n    rowIndegree[below]++;\n  }\n\n  // create colConditions graph and colIndegree\n  const colGraph = new Array(k).fill(null).map(() => new Array());\n  const colIndegree = new Array(k).fill(0);\n\n  for (let colCondition of colConditions) {\n    let [left, right] = colCondition;\n    left = left - 1;\n    right = right - 1;\n    colGraph[left].push(right);\n    colIndegree[right]++;\n  }\n\n  // topological sort (get row order)\n  const rowOrder = [];\n  let stack = [];\n\n  for (let i = 0; i < rowIndegree.length; i++) {\n    if (rowIndegree[i] === 0) {\n      stack.push(i);\n    }\n  }\n\n  while (stack.length) {\n    const current = stack.pop();\n    rowOrder.push(current);\n\n    for (let neighbor of rowGraph[current]) {\n      rowIndegree[neighbor]--;\n      if (rowIndegree[neighbor] === 0) {\n        stack.push(neighbor);\n      }\n    }\n  }\n\n  // check if matrix can satisfy all the conditions\n  if (rowOrder.length !== k) {\n    return [];\n  }\n\n  // topological sort (get col order)\n  const colOrder = [];\n  stack = [];\n\n  for (let i = 0; i < colIndegree.length; i++) {\n    if (colIndegree[i] === 0) {\n      stack.push(i);\n    }\n  }\n\n  while (stack.length) {\n    const current = stack.pop();\n    colOrder.push(current);\n\n    for (let neighbor of colGraph[current]) {\n      colIndegree[neighbor]--;\n      if (colIndegree[neighbor] === 0) {\n        stack.push(neighbor);\n      }\n    }\n  }\n\n  // check if matrix can satisfy all the conditions\n  if (colOrder.length !== k) {\n    return [];\n  }\n\n  // create the matrix and fill it using the row order and col order\n  const rowMap = rowOrder.reduce((acc, num, i) => {\n    acc[num] = i;\n    return acc;\n  }, {});\n\n  const colMap = colOrder.reduce((acc, num, i) => {\n    acc[num] = i;\n    return acc;\n  }, {});\n\n  const matrix = new Array(k).fill(null).map(() => new Array(k).fill(0));\n  for (let i = 0; i < k; i++) {\n    matrix[rowMap[i]][colMap[i]] = i + 1; // we need to add 1 again because before we decrement 1 to insert into graph.\n  }\n\n  return matrix;\n};\n```
['Graph', 'Topological Sort', 'JavaScript']