Simple || Easy ||Basic Understanding Approach || step by step || optimized ||Kahn algorithm||O(N)
Simple || Easy || Basic Understanding Approach || step by step || optimized|| Kahn algorithm || O(N) \n\nBuild a Matrix With Conditions\n\n# Intuition\n1. Intui
Simple || Easy || Basic Understanding Approach || step by step || optimized|| Kahn algorithm || O(N) \n\nBuild a Matrix With Conditions\n\n# Intuition\n1. Intuition in very simple we need to make a matrix by given condition where we have 2d matrix consist of row (above, bottom) and col (left,right). \n2. we can assume these 2 matrix in form of graph and try to execute a order of there arrival from (top to bottom) in row and (left to right) in col.\n3. Then this order will consider to making matix\n4. Simply put the element which appear in ith and jth position in row and col respectively in ans[i][j].\n5. remember that only 1 to k element are there. That means each row and col consist on only 1 element. which make it more simple to execute as we don\'t need to take care of other elements that would be 0.\n\n\n# Approach\n1. Execute a 2 vector of order (top to bottom) and (left to right).\n2. use concent of topology sort to get a perfet order of node which have visited 1st.\n3. After getting there order if there Present Cyclic nature in graph or we can say that given condition of row and col are not a DAG(direct acycylic graph) then we simply return empty vector as there is no such matrix present.\n     ```\n     if(r.size()==0||c.size()==0){\n            return {};\n        }\n4. we can simply put element in ans matix where r[i]=c[j] in ans[i][j]\n and remaining will be 0.\n    ```\n    for(int i=0;i<k;i++){\n            for(int j=0;j<k;j++){\n                if(r[i]==c[j]){\n                    ans[i][j]=r[i];\n                }\n            }\n        }\n\nTOPOLOGY SORT (APPROCH)\n1. convert 2d vector to addecent array\n   ```\n   for(auto it: num){\n            adj[it[0]].push_back(it[1]);\n        }\n\n2. then execute indegree of size k+1 of each element from 1 to k.\n   ```\n   for(int i=1;i<=n;i++){\n            for(auto it: adj[i]){\n                indegree[it]++;\n            }\n        }\n3. where we get indegree as 0 push that in queue as it is note dependent on any other element\n   ```\n   for(int i=1;i<=n;i++){\n            if(indegree[i]==0){\n                q.push(i);\n            }\n        }\n3. now simply execute a BFS traversal and push the node =q.front() in ans array \n4. decrease the indegree count of all node dependent on node which was on front.\n    ```\n   while(q.size()!=0){\n            auto node = q.front();\n            q.pop();\n            ans.push_back(node);\n            for(auto it: adj[node]){\n                indegree[it]--;\n                if(indegree[it]==0){\n                    q.push(it);\n                }\n            }\n        }\n5. if we get our array ans size = n that means no cyclic nature present in graph then we return ans. else empty array.\n   ```\n   if(ans.size()==n){\n            return ans;\n        }\n        return {};\n\n# Complexity\n- Time complexity:\nO(K)\n\n- Space complexity:\nO(K+K);\n\n# Code\n```\nclass Solution {\npublic:\n    \n    vector<int> topology(vector<vector<int>> num, int n){\n        vector<int> adj[n+1];\n        for(auto it: num){\n            adj[it[0]].push_back(it[1]);\n        }\n        vector<int> indegree(n+1,0);\n        for(int i=1;i<=n;i++){\n            for(auto it: adj[i]){\n                indegree[it]++;\n            }\n        }\n        queue<int> q;\n        for(int i=1;i<=n;i++){\n            if(indegree[i]==0){\n                q.push(i);\n            }\n        }\n        vector<int> ans;\n        while(q.size()!=0){\n            auto node = q.front();\n            q.pop();\n            ans.push_back(node);\n            for(auto it: adj[node]){\n                indegree[it]--;\n                if(indegree[it]==0){\n                    q.push(it);\n                }\n            }\n        }\n        if(ans.size()==n){\n            return ans;\n        }\n        return {};\n    }\n\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& row, vector<vector<int>>& col) {\n        int n = row.size();\n        int m = col.size();\n        vector<vector<int>> ans(k,vector<int>(k,0));\n\n        vector<int> r= topology(row,k);\n        vector<int> c = topology(col,k);\n        if(r.size()==0||c.size()==0){\n            return {};\n        }\n        for(int i=0;i<k;i++){\n            for(int j=0;j<k;j++){\n                if(r[i]==c[j]){\n                    ans[i][j]=r[i];\n                }\n            }\n        }\n\n        return ans;\n\n\n    }\n};\n```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++']