Beats 100% || Made it easy for you || C++|| Topological Sort || Matrix Filling
\n### Problem Breakdown\n\n1. Topological Sorting: The problem can be translated into a graph problem where rowConditions and colConditions provide directed edg
\n### Problem Breakdown\n\n1. **Topological Sorting**: The problem can be translated into a graph problem where `rowConditions` and `colConditions` provide directed edges indicating the order of elements in rows and columns respectively.\n2. **Matrix Construction**: Once the topological orderings are obtained, we need to position each element in the matrix such that they conform to both row and column orderings.\n\n### Approach\n\n1. **Topological Sort**: For both `rowConditions` and `colConditions`, perform a topological sort to determine the order of elements in rows and columns.\n2. **Matrix Filling**: Using the obtained topological orders, fill the matrix such that each element \\(i\\) is placed at the intersection of its determined row and column.\n\n### Detailed Steps\n\n1. **Topological Sorting**:\n   - **Adjacency List Construction**: For each condition, build an adjacency list.\n   - **DFS for Cycle Detection and Order**: Use Depth-First Search (DFS) to detect cycles (which would imply an invalid ordering) and to produce a topological order.\n   \n2. **Matrix Filling**:\n   - **Create Matrix**: Initialize a \\(k \\times k\\) matrix filled with zeros.\n   - **Position Elements**: Iterate through the topological orders and place each element at the intersection of its respective row and column order indices.\n\n### Code Explanation\n\n#### `buildMatrix` Function\nThis function coordinates the entire process:\n\n```cpp\nvector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n    // Store the topologically sorted sequences.\n    vector<int> orderRows = topoSort(rowConditions, k);\n    vector<int> orderColumns = topoSort(colConditions, k);\n\n    // If no topological sort exists, return empty array.\n    if (orderRows.empty() or orderColumns.empty()) return {};\n\n    vector<vector<int>> matrix(k, vector<int>(k, 0));\n    for (int i = 0; i < k; i++) {\n        for (int j = 0; j < k; j++) {\n            if (orderRows[i] == orderColumns[j]) {\n                matrix[i][j] = orderRows[i];\n            }\n        }\n    }\n    return matrix;\n}\n```\n\n1. **Topological Sorting**: Calls `topoSort` for rows and columns.\n2. **Matrix Initialization**: Creates an empty matrix of size \\(k \\times k\\).\n3. **Element Placement**: Places elements in the matrix based on their positions in `orderRows` and `orderColumns`.\n\n#### `topoSort` Function\nPerforms topological sorting using DFS:\n\n```cpp\nvector<int> topoSort(vector<vector<int>>& edges, int n) {\n    vector<vector<int>> adj(n + 1);\n    vector<int> order;\n    vector<int> visited(n + 1, 0);\n    bool hasCycle = false;\n\n    // Build adjacency list\n    for (auto& x : edges) {\n        adj[x[0]].push_back(x[1]);\n    }\n\n    // Perform DFS for each node\n    for (int i = 1; i <= n; i++) {\n        if (visited[i] == 0) {\n            dfs(i, adj, visited, order, hasCycle);\n            if (hasCycle) return {};\n        }\n    }\n    reverse(order.begin(), order.end());\n    return order;\n}\n```\n\n1. **Adjacency List**: Builds adjacency list from edge list.\n2. **DFS Initialization**: Starts DFS for unvisited nodes.\n3. **Cycle Detection**: Returns empty order if a cycle is detected.\n\n#### `dfs` Function\nHandles the DFS traversal and cycle detection:\n\n```cpp\nvoid dfs(int node, vector<vector<int>>& adj, vector<int>& visited,\n         vector<int>& order, bool& hasCycle) {\n    visited[node] = 1;  // Mark node as visiting\n    for (int neighbor : adj[node]) {\n        if (visited[neighbor] == 0) {\n            dfs(neighbor, adj, visited, order, hasCycle);\n            if (hasCycle) return;\n        } else if (visited[neighbor] == 1) {\n            // Cycle detected\n            hasCycle = true;\n            return;\n        }\n    }\n    visited[node] = 2;  // Mark node as visited\n    order.push_back(node);\n}\n```\n\n1. **Mark as Visiting**: Marks the node as currently visiting.\n2. **Recurse on Neighbors**: Recursively visits all unvisited neighbors.\n3. **Cycle Check**: Checks for back edges indicating cycles.\n4. **Mark as Visited**: Marks the node as fully visited and adds it to the order list.\n\n### Complexity Analysis\n\n- **Time Complexity**:\n  - **Topological Sorting**: \\(O(V + E)\\), where \\(V\\) is the number of nodes (in this case \\(k\\)) and \\(E\\) is the number of edges (conditions).\n  - **Matrix Filling**: \\(O(k^2)\\) for positioning elements in the matrix.\n  \n- **Space Complexity**:\n  - **Adjacency List**: \\(O(V + E)\\).\n  - **Visited Array and Order List**: \\(O(V)\\).\n\nThis approach ensures that the matrix is constructed correctly if valid topological orders exist for both rows and columns, and handles invalid cases by returning an empty matrix.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,\n                                    vector<vector<int>>& colConditions) {\n        // Store the topologically sorted sequences.\n        vector<int> orderRows = topoSort(rowConditions, k);\n        vector<int> orderColumns = topoSort(colConditions, k);\n\n        // If no topological sort exists, return empty array.\n        if (orderRows.empty() or orderColumns.empty()) return {};\n\n        vector<vector<int>> matrix(k, vector<int>(k, 0));\n        for (int i = 0; i < k; i++) {\n            for (int j = 0; j < k; j++) {\n                if (orderRows[i] == orderColumns[j]) {\n                    matrix[i][j] = orderRows[i];\n                }\n            }\n        }\n        return matrix;\n    }\n\nprivate:\n    vector<int> topoSort(vector<vector<int>>& edges, int n) {\n        vector<vector<int>> adj(n + 1);\n        vector<int> order;\n        // 0: not visited, 1: visiting, 2: visited\n        vector<int> visited(n + 1, 0);\n        bool hasCycle = false;\n\n        // Build adjacency list\n        for (auto& x : edges) {\n            adj[x[0]].push_back(x[1]);\n        }\n\n        // Perform DFS for each node\n        for (int i = 1; i <= n; i++) {\n            if (visited[i] == 0) {\n                dfs(i, adj, visited, order, hasCycle);\n                // Return empty if cycle detected\n                if (hasCycle) return {};\n            }\n        }\n        // Reverse to get the correct order\n        reverse(order.begin(), order.end());\n        return order;\n    }\n\n    void dfs(int node, vector<vector<int>>& adj, vector<int>& visited,\n             vector<int>& order, bool& hasCycle) {\n        visited[node] = 1;  // Mark node as visiting\n        for (int neighbor : adj[node]) {\n            if (visited[neighbor] == 0) {\n                dfs(neighbor, adj, visited, order, hasCycle);\n                // Early exit if a cycle is detected\n                if (hasCycle) return;\n            } else if (visited[neighbor] == 1) {\n                // Cycle detected\n                hasCycle = true;\n                return;\n            }\n        }\n        // Mark node as visited\n        visited[node] = 2;\n        // Add node to the order\n        order.push_back(node);\n    }\n};\n```\n\n\n\n![e76411b8-a184-4974-8098-a5792b2667a8_1708225665.6591249.png](https://assets.leetcode.com/users/images/d6aab4b7-dd35-4a60-9532-541352a97e3a_1721549511.5426884.png)\n
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++']