Solving Algorithmic Problems

Description   Solution: Topological Sort Use topological sort to find the order that each number should appear for both row and column conditions. If we can't process all nodes in the topological sort, that means we have a cycle and we return an empty matrix. Time Complexity:  O(k^2)  299ms Space Complexity:  O(k)  (not including output) 61MB var buildMatrix = function ( k, rowConditions, colConditions ) { let rowOrder = getOrder(k + 1 , rowConditions); let colOrder = getOrder(k + 1 , colConditions); if (rowOrder === - 1 || colOrder === - 1 ) return []; let matrix = Array (k).fill( 0 ).map( () => Array (k).fill( 0 )); let pos = Array (k + 1 ).fill( 0 ).map( () => Array ( 2 )); for ( let i = 0 ; i < k; i++) { pos[rowOrder[i]][ 0 ] = i; pos[colOrder[i]][ 1 ] = i; } for ( let i = 1 ; i <= k; i++) { let [x, y] = pos[i]; matrix[x][y] = i; } return matrix; }; function getOrder ( n, edges ) { let inde...

Description   Solution 1: Topological Sort on Reversed Graph Reverse the graph - we want to traverse the nodes backwards (starting from terminal nodes) Topological sort on the reversed graph, Any nodes that end up with an indegree of 0 is a safe node. n = number of nodes ,  m = number of edges Time Complexity:  O(n log(n) + m)  (including sorting) 253ms Space Complexity:  O(n)  61MB var eventualSafeNodes = function ( graph ) { let n = graph.length, reversed = Array (n).fill( 0 ).map( () => []); let queue = [], indegrees = Array (n).fill( 0 ); for ( let i = 0 ; i < n; i++) { indegrees[i] = graph[i].length; if (indegrees[i] === 0 ) queue.push(i); for ( let node of graph[i]) { reversed[node].push(i); } } let res = []; while (queue.length) { let node = queue.shift(); res.push(node); for ( let i = reversed[node].length; i >= 0 ; i--) { let nei = reversed[node].pop(); indegrees[...