Construct a 2D Matrix with Conditions.
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, we need to determine the relative positioning of numbers in a ma
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, we need to determine the relative positioning of numbers in a matrix based on given row and column constraints. This is similar to a scheduling problem where tasks have dependencies. The dependencies in this case are the conditions given for rows and columns, which can be visualized as a directed graph. The topological sorting of this graph will give us the required order of numbers.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Graph Construction:\n    - Construct directed graphs for both row conditions and column conditions.\n    - Each node in the graph represents a number from 1 to k.\n    -   Directed edges in the graph represent the "above-below" and "left-right" conditions.\n2. Topological Sorting:\n    - Perform topological sorting on both the row graph and the column graph.\n    - If a cycle is detected in any of the graphs, it means that the conditions are contradictory, and thus, no valid matrix can be constructed.\n    - If no cycles are detected, the topological sort will give us the order in which numbers should appear in rows and columns.\n3. Matrix Construction:\n    - Use the order obtained from the topological sort to place the numbers in the matrix.\n    - Initialize a k x k matrix with zeros.\n    -   Place each number in the matrix at the position derived from the topological sorting of rows and columns.\n# Complexity\n- Time complexity:\n    - Constructing the graph takes $$O(n+m)$$, where $$n$$ is the number of row conditions and $$m$$ is the number of column conditions.\n    - Topological sorting also takes $$O(k+E)$$, where $$k$$ is the number of nodes (which is equal to the given k) and $$E$$ is the number of edges in the graph.\n    -  Constructing the final matrix takes$$O(k^2)$$ since we are initializing a k x k matrix and placing k elements in it.\n    -   Overall time complexity is $$O(k+n+m+k 2)$$, which simplifies to $$O(k^2)$$ assuming k is large.\n- Space complexity:\n    - Storing the graph takes $$O(k+E)$$.\n    -   Additional space for storing the in-degrees, the order of elements, and the final matrix results in $$O(k^2)$$ space.\n    - Overall space complexity is $$O(k^2)$$.\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        // Helper function to perform topological sort\n        auto topologicalSort = [](int k, const vector<vector<int>>& conditions) {\n            vector<vector<int>> graph(k + 1);\n            vector<int> inDegree(k + 1, 0);\n            \n            for (const auto& condition : conditions) {\n                graph[condition[0]].push_back(condition[1]);\n                inDegree[condition[1]]++;\n            }\n            \n            queue<int> q;\n            for (int i = 1; i <= k; ++i) {\n                if (inDegree[i] == 0) {\n                    q.push(i);\n                }\n            }\n            \n            vector<int> order;\n            while (!q.empty()) {\n                int node = q.front();\n                q.pop();\n                order.push_back(node);\n                \n                for (int neighbor : graph[node]) {\n                    if (--inDegree[neighbor] == 0) {\n                        q.push(neighbor);\n                    }\n                }\n            }\n            \n            if (order.size() != k) return vector<int>(); // Cycle detected\n            return order;\n        };\n        \n        vector<int> rowOrder = topologicalSort(k, rowConditions);\n        vector<int> colOrder = topologicalSort(k, colConditions);\n        \n        if (rowOrder.empty() || colOrder.empty()) return {}; // If there\'s a cycle\n        \n        unordered_map<int, int> rowPosition;\n        unordered_map<int, int> colPosition;\n        \n        for (int i = 0; i < k; ++i) {\n            rowPosition[rowOrder[i]] = i;\n            colPosition[colOrder[i]] = i;\n        }\n        \n        vector<vector<int>> result(k, vector<int>(k, 0));\n        for (int num = 1; num <= k; ++num) {\n            int row = rowPosition[num];\n            int col = colPosition[num];\n            result[row][col] = num;\n        }\n        \n        return result;\n    }\n};\n\n```
['Matrix', 'C++']