dfs

• DFS

  • Topological sort

  • search in an array

  • memorization

    • Reviewed

    • TODO

DFS

037.Sudoku-Solver (M+) 040.Combination-Sum-II (M+) 051.N-Queens (M) 131.Palindrome-Partitioning (M+) 291.Word-Pattern-II (M) 417.Pacific-Atlantic-Water-Flow (M) 200.Number-of-Islands (M) 282.Expression-Add-Operators (H) 312.Burst-Balloons (H-) 351.Android-Unlock-Patterns (H-) 399.Evaluate-Division (H-) 488.Zuma-Game (H-) 425.Word-Squares (H-) 959.Regions-Cut-By-Slashes (M+) 1306.Jump-Game-III (M) 1718.Construct-the-Lexicographically-Largest-Valid-Sequence (H-) 1723.Find-Minimum-Time-to-Finish-All-Jobs (H-) 1766.Tree-of-Coprimes (H-) 1778.Shortest-Path-in-a-Hidden-Grid (H-)

Topological sort

• There are basically two categories of methods for topological sort. The first one is greedy algorithm with O(|V|^2 + |E|) time complexity. The second is based on depth first search with O(|V| + |E|) time complexity. Here only discusses DFS based approach.

• When using DFS based approach, there are two cases which should be taken care of. The first one is what if there exists no topological order at all. The second is how to return topological order.

  • What if there exists no topological order - a cycle is detected.

    • How to detect cycle: use UNDISCOVERED, DISCOVERED, VISITED to represent three possible states of graph nodes. Use a Set<?> isDiscovered and Set<?> isVisited to record all history info. If met up with a node which has been discovered but not visited, then a cycle is detected.

    • How to handle cycle: return a boolean value (preferred) or throw an exception (not really suitable because they are expected cases)

  • What if need to return topological order

    • If do not need to detect cycle, could simply use a Stack<> order to record the visited node, namely using Set<?> discovered, Stack<?> visited

    • If need to detect cycle, namely using Set<?> discovered, LinkedHashSet<?> visited

      ```java public int[] getTopoOrder(Map> graph) { Set discovered = new HashSet<>(); Set visited = new LinkedHashSet<>(); for ( Integer node : graph.keySet() ) { if ( !discoverd.contains( node ) ) { if ( !topoSort( graph, node, discovered, visited ) ) { // a cycle is detected....error handling } } }

      return visited.stream().reverse().collect( Collectors.toL); int[] topoOrder = new int[visited.size()]; int pos = topoOrder.length - 1; for ( Integer node : visited ) { topoOrder[pos] = node; pos--; }

      return topoOrder; }

    /**

    • @return whether a cycle is detected

      */

      private boolean topoSort ( Map> graph, Integer startNode, Set discovered, Set visited )

      {

      discovered.add( startNode );

      for ( Integer neighbor : graph.get( startNode ) )

      {

       if ( !discovered.contains( neighbor ) )
       {
           if ( topoSort( graph, neighbor, discovered, visited ) )
           {
               return true;
           }
       }
       else if ( discovered.contains( neighbor ) 
               && !visited.contains( neighbor ) )
       {
           return true;
       }
       else
       {
           // already visited, do nothing
           ;
       }

      }

      visited.add( startNode );

      return false;

      }

      ```

search in an array

090.Subsets-II (M+) 301.Remove-Invalid-Parentheses (H) 473.Matchsticks-to-Square (M+) 491.Increasing-Subsequences (M) 698.Partition-to-K-Equal-Sum-Subsets (H-) 996.Number-of-Squareful-Arrays (H-) 1307.Verbal-Arithmetic-Puzzle (H) 1593.Split-a-String-Into-the-Max-Number-of-Unique-Substrings (M) 1681.Minimum-Incompatibility (H)

memorization

Reviewed

329.Longest-Increasing-Path-in-a-Matrix (M)

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        
        @lru_cache(maxsize=None)
        def dfs(x: int, y: int) -> int:
            directions = [[0, -1], [-1, 0], [1, 0], [0, 1]]
            
            result = 1
            for direction in directions:
                nextX = x + direction[0]
                nextY = y + direction[1]
                if 0 <= nextX < height and 0 <= nextY < width and matrix[nextX][nextY] > matrix[x][y]:
                    result = max(result, 1 + dfs(nextX, nextY))
                
            return result
        
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0

        height = len(matrix)
        width = len(matrix[0])
        result = 0
        for i in range(height):
            for j in range(width):
                result = max(dfs(i, j), result)
        
        return result

TODO

638.Shopping-Offers (M+) 403.Frog-Jump (M+) 489.Robot-Room-Cleaner (H) 546.Remove-Boxes (H+) 1340.Jump-Game-V (M+) 1815.Maximum-Number-of-Groups-Getting-Fresh-Donuts (H-)