✅💯🔥Explanations No One Will Give You🎓🧠VERY Detailed Approach🎯🔥Extremely Simple And Effective🔥
\n\n        \n            \n                I am lucky that whatever fear I have inside me, my desire to win is always stronger.\n                    \n        
\n<blockquote>\n        <p>\n            <b>\n                I am lucky that whatever fear I have inside me, my desire to win is always stronger.\n            </b>        \n        </p>\n        <p>\n            --- Serena Williams ---\n        </p>\n</blockquote>\n\n# \uD83D\uDC51Problem Explanation and Understanding:\n\n## \uD83C\uDFAF Problem Description\nYou are given an integer `k` and two 2d arrays `rowConditions` and `colConditions`. You need to create 2d matrix with sizes `k x k` where there\'s exactly k numbers from 1 to k and all other elements are 0. Elements in `rowConditions` and `colConditions` - arrays with 2 elements which just mean: `rowCondition[0] must be in a row ABOVE rowCondition[1]` and `colCondition[0] must be in a column LEFT to colCondition[1]`.\n\n## \uD83D\uDCE5\u2935\uFE0F Input:\n- Integer `k` representing sizes of the matrix\n- Integer 2d array `rowConditions` representing conditions for rows\n- Integer 2d array `colConditions` representing conditions for columns\n\n## \uD83D\uDCE4\u2934\uFE0F Output:\nThe valid matrix you created OR the empty array if such matrix doesn\'t exist\n\n---\n\n# 1\uFE0F\u20E3\uD83C\uDFC6 Approach: Topological Sorting With DFS\n\n# \uD83E\uDD14 Intuition\n**First of all - graphs is hard**. Okay, now forget about the graphs and let me explain how to think about this problem. \n- Let\'s make problem easier for us, what if we will consider only `rowConditions` and for a second forget about `colConditions`? Like imagine we have matrix `K x 1` so all we need to do is place numbers correctly according to row ordering in `rowConditions`. Let\'s say somehow we created this matrixes (now this doesn\'t matter how, because you want to understand the logic of the problem)\n\n![image.png](https://assets.leetcode.com/users/images/bdf45577-ad8f-4e1d-aa97-0e7cf63ae6cd_1721540927.6011138.png)\n\n- Okay, good, we know in which row every element will go, but what about columns? We want columns also to be *sorted* with `colConditions`. Can we do the same thing we did to rows? Absolutely, let\'s do this.\n\n![image.png](https://assets.leetcode.com/users/images/4a344190-bbd5-4958-99be-d19681906793_1721541165.6145718.png)\n\n- Let\'s say now we have correct orders for both rows and columns, we know for sure in which row element must be and in which column, can we now esaily construct matrix with this? Sure\n\n![image.png](https://assets.leetcode.com/users/images/ecc59b70-d871-4b7c-b967-c4955b71ca18_1721541687.1688151.png)\n\n- In fact, this is the whole logic for this problem. But let\'s think about some edge cases and implementing details.\n- First of all - we created these sortings for rows and columns by magic in the example but in fact behind this approach is algorithm *Topological Sorting*. Topological sorting - graph algorithm for directed graphs without cycles which just sort graph vertixes in manner `first comes my prerequisites (parents) then I come myself and only then come my childrens`\n\nThis is an example for topological sorting ([source](https://youtu.be/7J3GadLzydI?si=zpZ_A8oLRSNkGql4))\n\n![image.png](https://assets.leetcode.com/users/images/aa1ec3a9-3835-4482-9b73-94244cdb8065_1721542058.1893058.png)\n\nThe sequence created above is just one of the possible sorting. Topological sort isn\'t unique which means that there can be multiple answers for one graph. \n\n- How we will apply topological sort to our problem? Well, look at the my pictures above where I\'ve drawn relations between values as arrows. In fact, we can imagine for both rows and columns conditions as graph where given to us `rowConditions` and `colConditions` are edges for graph. This will look like this:\n\n![image.png](https://assets.leetcode.com/users/images/fb1f2679-f518-411e-9276-cbd9969b369c_1721542450.7621114.png)\n\nAnd now if you think about topological sorting of the row graph you will see that in fact there\'s actually two possible sorting.\n\n- The one edge case I want to consider before we move on to the code - when there will be the case where matrix is impossible to create? Well, let\'s look on one more example from the description:\n\n![image.png](https://assets.leetcode.com/users/images/a7fab693-5008-4808-8682-4a3d23702d65_1721542687.138037.png)\n\nDo you see the problem? When I was explaining topological sorting I mentioned that it works only for graphs with no cycle (Acyclic) but there\'s actually the cycle and also logic drawback if you think about it - 1 must be higher than 2, 2 must be higher than 3 (so this can be [1, 2, 3]) but now what?.... 3 must be higher than 1 which is impossible because of previous conditions.\n\nHope this all makes sense - if not or you have any doubts feel free to ask questions in the comments!\u2764\uFE0F\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- Define a nested helper function `dfs` for depth-first search:\n  - `dfs` takes five arguments: `src` (current node), `graph` (adjacency list), `visited` (set of visited nodes), `cur_path` (current path nodes), and `res` (result list).\n  - Return `False` if a cycle is detected (node is in `cur_path`) and `True` otherwise.\n  - Mark the node as visited and add it to the current path.\n  - Recursively call `dfs` for each neighbor; if any call returns `False`, return `False`.\n  - Backtrack by removing the node from the current path and add it to the result list. (so last nodes visited will be first at list, that\'s why we reverse list in topo_sort)\n\n- Define another helper function `topo_sort` for topological sorting:\n  - `topo_sort` takes `edges` (list of edges) as input.\n  - Build an adjacency list `graph` from the edges.\n  - Initialize `visited` and `cur_path` as empty sets, and `res` as an empty list.\n  - Perform DFS on all nodes from 1 to `k` using the `dfs` function.\n  - Return an empty list if a cycle is detected, otherwise return the result list reversed.\n\n- Perform topological sorting on `rowConditions` and `colConditions` using `topo_sort` and store the results in `row_sorting` and `col_sorting`.\n- If either sorting result is an empty list (there was a cycle), return an empty list.\n- Create a dictionary `value_position` to store the row and column indices for each value from 1 to `k`.\n- Assign row indices to the values based on `row_sorting`.\n- Assign column indices to the values based on `col_sorting`.\n- Initialize the result matrix `res` as a `k x k` matrix filled with zeros.\n- Populate the matrix `res` using the positions from `value_position`.\n- Return the populated matrix `res`.\n\n# \uD83D\uDCD5 Complexity Analysis\n- \u23F0 Time complexity: O(k), since you will run 2 dfs on `k` nodes and visit each exactly once -> O(2k) -> O(k) (You can also consider O(k^2) since you\'re created matrix k x k but there\'s no way to return matrix without creating it, so this doesn\'t make sense)\n- \uD83E\uDDFA Space complexity: O(k), since we use several data structures like arrays and hashmaps with size up to `k` and there\'s dfs call stack which is also linear for `k`\n\n# \uD83D\uDCBB Code (I\'ve saved comments for each language)\n``` python []\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:\n        # return True if all okay and return False if cycle was found\n        def dfs(src, graph, visited, cur_path, res) -> bool:\n            if src in cur_path:\n                return False  # cycle detected\n\n            if src in visited:\n                return True  # all okay, but we\'ve already visited this node\n\n            visited.add(src)\n            cur_path.add(src)\n\n            for neighbor in graph[src]:\n                if not dfs(neighbor, graph, visited, cur_path, res):  # if any child returns false\n                    return False\n\n            cur_path.remove(src)  # backtrack path\n            res.append(src)\n            return True\n\n        # if there will be cycle - return empty array, in other case return 1d array as described above\n        def topo_sort(edges) -> list[int]:\n            graph = defaultdict(list)\n            for src, dst in edges:\n                graph[src].append(dst)\n\n            visited: set[int] = set()\n            cur_path: set[int] = set()\n            res: list[int] = []\n\n            for src in range(1, k + 1, 1):\n                if not dfs(src, graph, visited, cur_path, res):\n                    return []\n\n            return res[::-1]  # we will have res as reversed so we need to reverse it one more time\n\n        row_sorting: list[int] = topo_sort(rowConditions)\n        col_sorting: list[int] = topo_sort(colConditions)\n        if [] in (row_sorting, col_sorting):\n            return []\n\n        value_position: dict[int, list[int]] = {\n            n: [0, 0] for n in range(1, k + 1, 1)\n        }  # element -> [row_index, col_index]\n        for ind, val in enumerate(row_sorting):\n            value_position[val][0] = ind\n        for ind, val in enumerate(col_sorting):\n            value_position[val][1] = ind\n\n        res: list[list[int]] = [[0 for _ in range(k)] for _ in range(k)]\n        for value in range(1, k + 1, 1):\n            row, column = value_position[value]\n            res[row][column] = value\n\n        return res\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        unordered_map<int, vector<int>> graph;\n        for (const auto& edge : rowConditions) {\n            graph[edge[0]].push_back(edge[1]);\n        }\n\n        vector<int> row_sorting = topo_sort(graph, k);\n        graph.clear();\n        for (const auto& edge : colConditions) {\n            graph[edge[0]].push_back(edge[1]);\n        }\n        vector<int> col_sorting = topo_sort(graph, k);\n\n        if (row_sorting.empty() || col_sorting.empty()) {\n            return {};\n        }\n\n        unordered_map<int, pair<int, int>> value_position;\n        for (int i = 0; i < k; ++i) {\n            value_position[row_sorting[i]].first = i;\n            value_position[col_sorting[i]].second = i;\n        }\n\n        vector<vector<int>> res(k, vector<int>(k, 0));\n        for (int value = 1; value <= k; ++value) {\n            int row = value_position[value].first;\n            int column = value_position[value].second;\n            res[row][column] = value;\n        }\n\n        return res;\n    }\n\nprivate:\n    bool dfs(int src, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited, unordered_set<int>& cur_path, vector<int>& res) {\n        if (cur_path.count(src)) return false;  // cycle detected\n        if (visited.count(src)) return true;  // all okay, but we\'ve already visited this node\n\n        visited.insert(src);\n        cur_path.insert(src);\n\n        for (int neighbor : graph[src]) {\n            if (!dfs(neighbor, graph, visited, cur_path, res))  // if any child returns false\n                return false;\n        }\n\n        cur_path.erase(src);  // backtrack path\n        res.push_back(src);\n        return true;\n    }\n\n    vector<int> topo_sort(unordered_map<int, vector<int>>& graph, int k) {\n        unordered_set<int> visited;\n        unordered_set<int> cur_path;\n        vector<int> res;\n\n        for (int src = 1; src <= k; ++src) {\n            if (!dfs(src, graph, visited, cur_path, res))\n                return {};\n        }\n\n        reverse(res.begin(), res.end());  // we will have res as reversed so we need to reverse it one more time\n        return res;\n    }\n};\n```\n``` JavaScript []\nvar buildMatrix = function(k, rowConditions, colConditions) {\n    // return True if all okay and return False if cycle was found\n    function dfs(src, graph, visited, cur_path, res) {\n        if (cur_path.has(src)) return false;  // cycle detected\n        if (visited.has(src)) return true;  // all okay, but we\'ve already visited this node\n\n        visited.add(src);\n        cur_path.add(src);\n\n        for (let neighbor of (graph.get(src) || [])) {\n            if (!dfs(neighbor, graph, visited, cur_path, res))  // if any child returns false\n                return false;\n        }\n\n        cur_path.delete(src);  // backtrack path\n        res.push(src);\n        return true;\n    }\n\n    // if there will be cycle - return empty array, in other case return 1d array as described above\n    function topo_sort(edges) {\n        let graph = new Map();\n        for (let [src, dst] of edges) {\n            if (!graph.has(src)) graph.set(src, []);\n            graph.get(src).push(dst);\n        }\n\n        let visited = new Set();\n        let cur_path = new Set();\n        let res = [];\n\n        for (let src = 1; src <= k; ++src) {\n            if (!dfs(src, graph, visited, cur_path, res))\n                return [];\n        }\n\n        return res.reverse();  // we will have res as reversed so we need to reverse it one more time\n    }\n\n    let row_sorting = topo_sort(rowConditions);\n    let col_sorting = topo_sort(colConditions);\n    if (!row_sorting.length || !col_sorting.length)\n        return [];\n\n    let value_position = {};\n    for (let n = 1; n <= k; ++n) {\n        value_position[n] = [0, 0];  // element -> [row_index, col_index]\n    }\n    row_sorting.forEach((val, ind) => value_position[val][0] = ind);\n    col_sorting.forEach((val, ind) => value_position[val][1] = ind);\n\n    let res = Array.from({ length: k }, () => Array(k).fill(0));\n    for (let value = 1; value <= k; ++value) {\n        let [row, column] = value_position[value];\n        res[row][column] = value;\n    }\n\n    return res;\n};\n```\n``` Java []\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        List<Integer> row_sorting = topo_sort(rowConditions, k);\n        List<Integer> col_sorting = topo_sort(colConditions, k);\n        if (row_sorting.isEmpty() || col_sorting.isEmpty())\n            return new int[0][0];\n\n        Map<Integer, int[]> value_position = new HashMap<>();\n        for (int n = 1; n <= k; ++n) {\n            value_position.put(n, new int[2]);  // element -> [row_index, col_index]\n        }\n        for (int ind = 0; ind < row_sorting.size(); ++ind) {\n            value_position.get(row_sorting.get(ind))[0] = ind;\n        }\n        for (int ind = 0; ind < col_sorting.size(); ++ind) {\n            value_position.get(col_sorting.get(ind))[1] = ind;\n        }\n\n        int[][] res = new int[k][k];\n        for (int value = 1; value <= k; ++value) {\n            int row = value_position.get(value)[0];\n            int column = value_position.get(value)[1];\n            res[row][column] = value;\n        }\n\n        return res;\n    }\n\n    // return True if all okay and return False if cycle was found\n    private boolean dfs(int src, Map<Integer, List<Integer>> graph, Set<Integer> visited, Set<Integer> cur_path, List<Integer> res) {\n        if (cur_path.contains(src)) return false;  // cycle detected\n        if (visited.contains(src)) return true;  // all okay, but we\'ve already visited this node\n\n        visited.add(src);\n        cur_path.add(src);\n\n        for (int neighbor : graph.getOrDefault(src, Collections.emptyList())) {\n            if (!dfs(neighbor, graph, visited, cur_path, res))  // if any child returns false\n                return false;\n        }\n\n        cur_path.remove(src);  // backtrack path\n        res.add(src);\n        return true;\n    }\n\n    // if there will be cycle - return empty array, in other case return 1d array as described above\n    private List<Integer> topo_sort(int[][] edges, int k) {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        for (int[] edge : edges) {\n            graph.computeIfAbsent(edge[0], x -> new ArrayList<>()).add(edge[1]);\n        }\n\n        Set<Integer> visited = new HashSet<>();\n        Set<Integer> cur_path = new HashSet<>();\n        List<Integer> res = new ArrayList<>();\n\n        for (int src = 1; src <= k; ++src) {\n            if (!dfs(src, graph, visited, cur_path, res))\n                return Collections.emptyList();\n        }\n\n        Collections.reverse(res);  // we will have res as reversed so we need to reverse it one more time\n        return res;\n    }\n}\n```\n\n## \uD83D\uDCA1\uD83D\uDCA1\uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning!\uD83D\uDCDA\n\n### Please consider *upvote*\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/fde74702-a4f6-4b9f-95f2-65fa9aa79c48_1716995431.3239644.png)\n
['Array', 'Hash Table', 'Graph', 'Topological Sort', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']