BFS - Intuition & Approach Explained C++
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen I first read the problem, I noticed that there was a dependency involved. Whenever
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen I first read the problem, I noticed that there was a dependency involved. Whenever we encounter dependency, we should think of graphs. Moreover, there was an additional constraint of ordering, which implies that we need to sort the elements in a specific order. Since we are given the conditions in the form of edges, we can simply apply topological sorting to resolve the dependencies and obtain the desired order\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Represent the condition dependency in the form of graph\n2. Sort the graph by topological sort\n3. Using the topological order obtained for rows and columns, construct the matrix such that each element is placed in the correct position respecting both row and column conditions.\n\n# Complexity\n- Time complexity: $$O(k+E)+O(k^2)=O(k^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(k^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n//topological sort, how?\n\n    //use BFS Kahn\'s algorithm\n    vector<int> topoSort(int k, vector<vector<int>> edges){\n        vector<vector<int>> graph(k+1);\n        vector<int> indegree(k+1,0);\n        vector<int> res;\n\n\n        //build graph & calculate indegrees\n        for(vector<int>& edge: edges){\n            graph[edge[0]].push_back(edge[1]);\n            indegree[edge[1]]++;\n        }\n\n        queue<int> q;\n        //push nodes with no dependency\n        for(int i=1; i<=k; i++){\n            if(indegree[i]==0){\n                q.push(i);\n            }\n        }\n        //BFS\n        while(!q.empty()){\n            int cur = q.front(); q.pop();\n            res.push_back(cur);\n\n            for(int neigh: graph[cur]){\n                indegree[neigh]--;\n                if(indegree[neigh]==0){\n                    q.push(neigh);\n                }\n            }\n        }\n        //check for cyle\n        for(int i=1; i<=k; i++){\n            if(indegree[i]!=0){\n                return {};\n            }\n        }\n        return res;\n    }\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n\n        vector<int> rowOrder = topoSort(k, rowConditions);\n        vector<int> colOrder = topoSort(k, colConditions);\n\n        //if we encountered a cycle in any condition, return empty array\n        if(rowOrder.empty() || colOrder.empty()){\n            return {};\n        }\n\n        vector<vector<int>> res(k, vector<int>(k,0));\n\n        //build the result matrix\n        for(int i=0; i<k; i++){\n            int ele = rowOrder[i];\n            for(int j=0; j<k; j++){\n                if(colOrder[j]==ele){\n                    res[i][j] = ele;\n                }\n            }\n        }\n        return res;\n    }\n};\n\n```
['Breadth-First Search', 'Graph', 'C++']