Simple and Clean C++ solution using kahn's algorithm
Intuition\nSimple idea behind the solution is if we take projections of non zero elements of matrix along the row and column , those projected rows and colums s
# Intuition\nSimple idea behind the solution is if we take projections of non zero elements of matrix along the row and column , those projected rows and colums should be topologically sorted. \nSo we will first find valid orders of row and columns. seperately and then we will form the matrix. \n\n\n```\nclass Solution {\npublic:\n    vector<int> validorder(vector<vector<int>> &conditions, int k){\n        vector<int> indegree(k+1, 0);\n        vector<vector<int>> adj(k+1);\n        // we will first create an adj list\n        for(int i = 0 ; i< conditions.size(); i++){\n            int a = conditions[i][0];\n            int b = conditions[i][1];\n            indegree[b]++;\n            adj[a].push_back(b);\n        }\n        //Kahn\'s algo\n        vector<int> order;\n        queue<int> q;\n        for(int i=1;i<=k;i++){\n            if(indegree[i]==0){\n                q.push(i);\n            }\n        }\n        while(!q.empty()){\n            int node = q.front();\n            q.pop();\n            order.push_back(node);\n            for(int i = 0 ; i<adj[node].size(); i++){\n                int x=adj[node][i];\n                indegree[x]--;\n                if(indegree[x]==0){\n                    q.push(x);\n                }\n            }\n        }\n        return order;\n    }\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<int> validcol = validorder(rowConditions, k);\n        vector<int> validrow = validorder(colConditions, k);\n\n        if(validcol.size()!=k||validrow.size()!=k) return {};\n\n        vector<vector<int>> validmatrix(k, vector<int>(k, 0));\n        for(int i = 0;i<k;i++){\n            for(int j = 0 ; j<k ; j++){\n                if(validcol[i]==validrow[j]){\n                    validmatrix[i][j]=validcol[i];\n                }\n            }\n        }\n        return validmatrix;\n    }\n};\n\n```\n![image.jpg](https://assets.leetcode.com/users/images/2f82ab47-0d5d-4801-a24c-fc6d86a6dce1_1678910941.9007642.jpeg)\n\nSaw a lot of solutions using this approach to form matrix , thought it was a little complicated.\n```\nvector<int> idx(k+1,0);\n        for(int j=0;j<validcol.size();j++){\n            idx[validcol[j]] = j;\n        }\n\n        vector<vector<int>> validmatrix(k, vector<int>(k, 0));\n        for(int i=0;i<k;i++){\n            validmatrix[i][idx[validrow[i]]] = validrow[i];\n        }\n```\n\n
['Breadth-First Search', 'Graph', 'Topological Sort', 'C++']