Easy Approach and Clear Structure ! Beats 100% in runtime ! #TopologicalSort
Intuition\n Describe your first thoughts on how to solve this problem. \nThink is problem as a "GRAPH" problem. The first and second number in x-conditions just
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThink is problem as a "GRAPH" problem. The first and second number in x-conditions just like a from u to v edge. Then, use topological sort to solve this problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**First**, we can convert the x-conditions as a graph. I store the graph as four parts: number of vertices \\ adjacency list \\ roots whose indegree are \'0\' \\ indegree of each vertice.\n\n**Second**, go on topological sort on row-Graph and col-Graph. I store the result in a map which indicates {vertice: index in row / col}. In the \'for\' loop, g.Roots acts as the queue for BFS. The top of the queue as it is popped out will be put in the order map with the val is which index it would be. And if its adjacent vertice\'s indegree is decrease to zero, I push this vertice into the queue, i.e. g.Roots.\n\n**Last**, just put the result in the return matrix.\n\n**Be careful** that in each step you need to check whether there exist cycle or not, i.e. the error condition in each function.\n\n# Complexity\n- Time complexity: $$O(N + E)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n![image.png](https://assets.leetcode.com/users/images/0db322fc-8779-4d0e-85a5-3f1fe2e8dddb_1721559243.6839113.png)\n\n\n# Code\n```\ntype Graph struct {\n    Verts   int\n    AdjList map[int][]int\n    Roots []int\n    Indegree map[int]int\n}\n\nfunc NewGraph(k int, conditions [][]int) (*Graph, error) {\n    g := Graph{\n        Verts: k,\n        AdjList: make(map[int][]int),\n        Roots: make([]int, 0),\n        Indegree: make(map[int]int),\n    }\n    for i := 1; i < k + 1; i += 1 {\n        g.Indegree[i] = 0\n    }\n    for _, cond := range conditions {\n        u, v := cond[0], cond[1]\n        g.AdjList[u] = append(g.AdjList[u], v)\n        g.Indegree[v] += 1\n    }\n    for key, val := range g.Indegree {\n        if val == 0 {\n            g.Roots = append(g.Roots, key)\n        }\n    }\n    if len(g.Roots) == 0 {\n        return nil, errors.New("")\n    }\n    return &g, nil\n}\n\nfunc (g *Graph) TopologicalSort() (map[int]int, error) {\n    order, idx := make(map[int]int), 0\n    for len(g.Roots) != 0 {\n        top := g.Roots[0]\n        g.Roots = g.Roots[1:]\n        order[top] = idx\n        idx += 1\n        for _, adj := range g.AdjList[top] {\n            g.Indegree[adj] -= 1\n            if g.Indegree[adj] == 0 {\n                g.Roots = append(g.Roots, adj)\n            }\n        }\n    }\n    if len(order) != g.Verts {\n        return nil, errors.New("")\n    }\n    return order, nil\n}\n\nfunc buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {\n    rowGraph, err := NewGraph(k, rowConditions)\n    if err != nil {\n        return make([][]int, 0)\n    }\n    colGraph, err := NewGraph(k, colConditions)\n    if err != nil {\n        return make([][]int, 0)\n    }\n\n    rowTopo, err := rowGraph.TopologicalSort()\n    if err != nil {\n        return make([][]int, 0)\n    }\n    colTopo, err := colGraph.TopologicalSort()\n    if err != nil {\n        return make([][]int, 0)\n    }\n    rowGraph, colGraph = nil, nil\n\n    ret := make([][]int, k)\n    for i := 0; i < k; i += 1 {\n        ret[i] = make([]int, k)\n    }\n\n    for i := 1; i < k + 1; i += 1 {\n        ret[rowTopo[i]][colTopo[i]] = i\n    }\n\n    return ret\n}\n```
['Go']