Solving Algorithmic Problems

Description   Solution 1: BFS & Binary Search Use multi-source BFS to find each cell's minimum distance to a thief. We start the BFS at the thief cells and expand outwards. Binary search for the maximum possible minSafeness factor. To check whether a minSafeness is possible, use BFS to check whether there exists a valid path from  (0, 0)  to  (n-1, n-1)  using only cells with  safeness >= minSafeness . Time Complexity:  O(n^2 log(n^2))  512ms Space Complexity:  O(n^2)  91.4MB var maximumSafenessFactor = function ( grid ) { let safeness = getSafeness(grid), n = grid.length; let low = 0 , high = n * n; while (low < high) { let mid = Math .ceil((low + high) / 2 ); if (isEnough(safeness, mid)) low = mid; else high = mid - 1 ; } return low; }; function isEnough ( safeness, minSafeness ) { // use bfs to check whether a valid path exists using only cells with safeness >= minSafeness let n = safen...

Description   Solution: BFS & DFS Since it's a tree, there is only one path between each pair of nodes. For each trip, use BFS to find the path from the start node to the end node. Keep track of totalPrice, where  totalPrice[i] = the total price from node i across all trips . Use DFS with memoization to find the minimum score from taking half price on non-alternate nodes. Memoize each  dfs(node, parentIsHalfPrice, parent) . If the parent is half price, then this node cannot be half price. If the parent is not half price, we have two choices: either take half price or don't take half price. Return the minimum price. n = number of nodes ,  m = number of trips Time Complexity:  O(m * n^2 + n^2) Space Complexity:  O(n) var minimumTotalPrice = function ( n , edges , price , trips ) { let graph = Array ( n ) . fill ( 0 ) . map ( ( ) => [ ] ) ; for ( let [ a , b ] of edges ) { graph [ a ] . push ( b ) ; graph [ b ] . push ( ...