C++ code using topological sort (using Kahn's algorithm)
IntuitionYou can think of each conditions in rowconditions and colconditions as a edge between two vertices.Make a topological sort the all the elements based o
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
You can think of each conditions in rowconditions and colconditions as a edge between two vertices.
Make a topological sort the all the elements based on the rowconditions and colconditions. According to it, find the position of each element in required matrix.
# Approach
<!-- Describe your approach to solving the problem. -->
Here i tried to find topological sort using kahn's algorithm. A valid topological sort if not possible if a cycle is present in the graph. So if valid toplogical sort is not possible, then return empty vector.
After finding valid topological sort, find the row and column for each element by using the element present at different indices. Fill the elements in the ans vector and return it.
Note that there was no need to clear the queue after finding the first vector "row" because the toposort function works until the queue is cleared, so queue becomes empty automatically.
# Complexity
- Time complexity: O(k+E)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(k^2)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    void toposort(unordered_map<int,int>& indegree,unordered_map<int, vector<int>>& adj, queue<int>& q, vector<int>& vec){
        while(!q.empty()){
            int k = q.front();
            q.pop();
            vec.push_back(k);
            for(int i : adj[k]){
                indegree[i]--;
                if(indegree[i] == 0) q.push(i);
            }
        }
    }
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        unordered_map<int, vector<int>> adjr, adjc;
        unordered_map<int, int> indr, indc;
        vector<int> row, col;
        queue<int> q;
        vector<vector<int>> ans(k, vector<int>(k, 0)), empty;
        vector<pair<int,int>> last(k, {0,0});

        for(int i = 1;i<=k;i++){
            indr[i] = 0;
            indc[i] = 0;
        }
        for(auto i : rowConditions){
            adjr[i[0]].push_back(i[1]);
            indr[i[1]]++;
        }
        for(auto i : colConditions){
            adjc[i[0]].push_back(i[1]);
            indc[i[1]]++;
        }
        for(auto i : indr){
            if(i.second == 0) q.push(i.first);
        }
        toposort(indr, adjr, q, row);
        if(row.size() != k) return empty;
        for(auto i : indc){
            if(i.second == 0) q.push(i.first);
        }
        toposort(indc, adjc, q, col);
        if(col.size() != k) return empty;
        for(int i = 0;i<k;i++){
            last[row[i] - 1].first = i;
        }
        for(int i = 0;i<k;i++){
            last[col[i] - 1].second = i;
        }

        for(int i = 0;i<k;i++){
            ans[last[i].first][last[i].second] = i+1;
        }
        return ans;
    }
};
```
['C++']