Dynamic Programming with DFS

31. Longest Increasing Path in a Matrix (329)

1. Problem Description: The problem "Longest Increasing Path in a Matrix" can be found on LeetCode at the following link: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

2. Optimized Java Code:

// This is the optimized java code for the problem "Longest Increasing Path in a Matrix"

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int maxPathLength = 1;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] memo = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int pathLength = dfs(matrix, i, j, memo);
                maxPathLength = Math.max(maxPathLength, pathLength);
            }
        }
        
        return maxPathLength;
    }
    
    private int dfs(int[][] matrix, int i, int j, int[][] memo) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        
        int maxPath = 1;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        for (int[] dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[x][y] > matrix[i][j]) {
                int pathLength = 1 + dfs(matrix, x, y, memo);
                maxPath = Math.max(maxPath, pathLength);
            }
        }
        
        memo[i][j] = maxPath;
        return maxPath;
    }
}

1. Algorithm and Approach: In this problem, the goal is to find the length of the longest increasing path in a matrix. An increasing path is defined as a path starting from any cell and moving to a neighbor cell (up, down, left, or right) with a higher value. The path can only move to neighboring cells with a strictly increasing value.

   The approach we will use to solve this problem is memoization with depth-first search (DFS). We will create a memoization array to store the length of the longest increasing path starting from each cell. We will start DFS from each cell in the matrix, and for each cell, we will recursively explore its neighbors to find the longest increasing path starting from that cell. We will use the memoization array to avoid recomputing the same path multiple times.

   The main steps of the algorithm are as follows:

   • Create a memo[][] array of the same size as the input matrix to store the length of the longest increasing path starting from each cell.

   • Initialize a variable maxPathLength to keep track of the maximum path length found so far.

   • Iterate through each cell of the matrix using nested loops.

     • For each cell, call the dfs() function to find the length of the longest increasing path starting from that cell.

     • Update maxPathLength with the maximum path length found so far.

   • Return the maxPathLength as the result.

   The dfs() function is a helper function that performs the depth-first search to find the length of the longest increasing path starting from a given cell. It uses a directions[] array to define the four possible directions (up, down, left, right) to move to the neighboring cells. For each valid neighbor, it recursively calls dfs() and updates the maxPath variable with the maximum path length found so far. Before returning the result, the function updates the memo[][] array with the maxPath value for the current cell, to avoid recomputing it in the future.

   During an interview, it's important to communicate the approach clearly and step by step. You can also discuss the time and space complexity of the solution. In this case, the time complexity of the solution is O(rows * cols) as we visit each cell exactly once. The space complexity is also O(rows * cols) to store the memoization array.

32. Max Area of Island (695)

1. Problem Description and Link: The problem "Max Area of Island" is a popular problem on LeetCode. The problem can be found at the following link: https://leetcode.com/problems/max-area-of-island/

2. Solution in Java:

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
    
    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        int area = 1;
        area += dfs(grid, i-1, j);
        area += dfs(grid, i+1, j);
        area += dfs(grid, i, j-1);
        area += dfs(grid, i, j+1);
        return area;
    }
}

1. Algorithm and Thinking Process: The problem asks us to find the maximum area of an island in a given grid. An island is represented by '1' in the grid, and the area of an island is the number of connected '1's.

To solve this problem, we can iterate through each cell in the grid. If we find a '1', we start a Depth-First Search (DFS) to visit all the connected '1's. During the DFS, we mark the visited cells as '0' to avoid counting them again. We keep track of the maximum area we have found so far and update it whenever we encounter a larger area.

During an interview, it is important to communicate your thought process clearly. Here are some steps you can follow to describe the algorithm during an interview:

1. Explain that we will iterate through each cell in the grid.

2. When we find a '1', we will start a DFS to visit all connected '1's and calculate the area.

3. In the DFS, we mark visited cells as '0' to avoid counting them again.

4. We keep track of the maximum area we have found so far and update it whenever we find a larger area.

5. Finally, we return the maximum area as the result.

By explaining your algorithm clearly and providing a well-optimized code solution with detailed comments, you can showcase your problem-solving skills to the interviewer. Remember to consider edge cases and test the code thoroughly before providing the final solution.

33. All Paths from Source to Target (797)

1. Problem description and link: The problem "All Paths from Source to Target" is a graph problem that asks you to find all possible paths from a source node to a target node in a directed graph. You are given a graph in the form of an adjacency list, where the index represents the node and the value represents the neighbors of that node. The goal is to return a list of all paths from the source node to the target node.

LeetCode link: https://leetcode.com/problems/all-paths-from-source-to-target/

1. Optimized Java code with comments:

import java.util.*;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        currentPath.add(0); // Start from the source node (0)
        dfs(graph, 0, currentPath, result); // Call the depth-first search function
        return result;
    }
    
    private void dfs(int[][] graph, int node, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == graph.length - 1) { // If we reach the target node
            result.add(new ArrayList<>(currentPath)); // Add the current path to the result
            return;
        }
        
        for (int neighbor : graph[node]) { // Iterate through the neighbors of the current node
            currentPath.add(neighbor); // Add the neighbor to the current path
            dfs(graph, neighbor, currentPath, result); // Recursively call dfs on the neighbor
            currentPath.remove(currentPath.size() - 1); // Remove the neighbor from the current path
        }
    }
}

1. Algorithm and thinking process during an interview:

The problem asks for finding all possible paths from a source node to a target node in a directed graph. The given graph is represented as an adjacency list.

To solve this problem, we can use a depth-first search (DFS) algorithm. We start from the source node and keep traversing the graph by recursively visiting its neighbors until we reach the target node. During the DFS traversal, we maintain a current path list that keeps track of the nodes visited so far.

Here is a step-by-step approach to solve this problem:

1. Initialize an empty result list and an empty current path list. Add the source node (0) to the current path.

2. Implement the DFS algorithm with backtracking. In the DFS function, if the current node is the target node (graph.length - 1), add the current path to the result list and return. Otherwise, iterate through the neighbors of the current node and recursively call DFS on each neighbor.

3. Inside the DFS loop, add the current neighbor to the current path, call DFS on the neighbor, and then remove the neighbor from the current path.

4. After the DFS loop, return the result list.

During an interview, it is essential to communicate your approach and algorithm clearly to the interviewer. Explain that you will use the DFS algorithm to traverse the graph and find all the paths from the source to the target. Mention that DFS is an efficient algorithm for searching all possible paths in a graph. Walk through the code and discuss the purpose of each step, including adding/removing nodes from the current path and updating the result list.

Make sure to test your code with multiple test cases, including different graph structures, to ensure its correctness.

34. Word Break II (140)

1. Problem Description: Word Break II (140)

   • Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

   • Note:

     • The same word in the dictionary may be reused multiple times in the segmentation.

     • You may assume the dictionary does not contain duplicate words.

   • Problem Link: Word Break II
2. Optimized Java Code:

import java.util.*;

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        // We will use a HashMap to store the results of each substring
        // This will help avoid redundant computations
        HashMap<String, List<String>> memo = new HashMap<>();
        return wordBreakHelper(s, wordDict, memo);
    }
    
    private List<String> wordBreakHelper(String s, List<String> wordDict, HashMap<String, List<String>> memo) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        
        List<String> result = new ArrayList<>();
        
        // Base case: if s is an empty string, return an empty list
        if (s.length() == 0) {
            return result;
        }
        
        // Checking if s itself is in the wordDict
        if (wordDict.contains(s)) {
            result.add(s);
        }
        
        // Checking all possible prefixes of s
        for (int i = 1; i < s.length(); i++) {
            String prefix = s.substring(0, i);
            
            // If the prefix is in wordDict, recursively check the remaining suffix of s
            if (wordDict.contains(prefix)) {
                String suffix = s.substring(i);
                List<String> suffixResult = wordBreakHelper(suffix, wordDict, memo);
                
                // Building all possible sentences using the prefix and the suffix results
                for (String sentence : suffixResult) {
                    result.add(prefix + " " + sentence);
                }
            }
        }
        
        // Memoize the result for current substring
        memo.put(s, result);
        return result;
    }
}

1. Detailed Description:

• The problem can be solved using a recursive approach with memoization.

• We use a HashMap memo to store the results for each substring. This will help avoid redundant computations for the same substring.

• In the wordBreak method, we initialize the memo HashMap and call the wordBreakHelper method to calculate the result for the given string s and word dictionary wordDict.

• In the wordBreakHelper method, we first check if the result for the current substring s is already present in the memo HashMap. If yes, we return the result from the memo.

• The base case for recursion is when the length of s is 0, which means we have reached the end of the string. In such cases, we return an empty list.

• We then check if the current string s itself is present in the wordDict. If yes, we add it to the result list as a valid sentence.

• Then, we iterate over all possible prefixes of the string s and check if the prefix is present in the wordDict. If yes, we recursively call the wordBreakHelper method for the remaining suffix of s (i.e., from index i to the end) and store the result in the suffixResult list.

• Finally, we iterate over the suffixResult list and append each sentence with the current prefix, separated by a space. We add these sentences to the result list.

• Finally, we memoize the result list for the current substring s in the memo HashMap and return the result.

• During an interview, it is important to understand the problem requirements and constraints. In this problem, we are given a string and a word dictionary, and we need to generate all possible sentences by adding spaces to the given string such that each word formed is present in the dictionary. The same word in the dictionary can be reused multiple times. We need to return all such possible sentences.

• To solve this problem, we can use a recursive approach with memoization. We break the problem into smaller subproblems by considering all possible prefixes of the given string. For each prefix, we recursively check the remaining suffix and generate all sentences using the current prefix. We store the results for each substring in a HashMap to avoid redundant computations.

• While implementing the solution, we need to consider corner cases such as an empty string or an empty word dictionary. We also need to handle cases where a prefix is present in the dictionary but the remaining suffix does not form valid sentences.

• It is a good practice to discuss the time and space complexity of the solution. In this case, the time complexity is O(n^3) as we are iterating through all possible substrings and each substring can have a length up to n, where n is the length of the given string. The space complexity is O(n^2) due to the memoization HashMap.

35. Unique Paths III (980)

1. Problem Description: The problem "Unique Paths III" is described as follows: You are given a 2D grid of size m x n, where each cell represents an obstacle or empty space. Starting from the top-left corner, you want to reach the bottom-right corner, while traveling through empty spaces. The only allowed movements are right and down. Some cells may be blocked and you cannot enter those cells. There is also a start cell and an end cell, denoted by 1 and 2 respectively. Your goal is to find the unique paths from the start to the end cell, where a unique path is defined as a sequence of cells visited such that all visited cells are distinct.

LeetCode Link: https://leetcode.com/problems/unique-paths-iii/

1. Optimized Java Code with Detailed Comments:

class Solution {
    private int numOfPaths = 0; // Variable to store the number of unique paths
    
    public int uniquePathsIII(int[][] grid) {
        int startX = 0; // X-coordinate of the start cell
        int startY = 0; // Y-coordinate of the start cell
        int emptyCount = 1; // Count of empty cells (excluding start cell)
        
        // Find the start cell and count empty cells
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] == 0) {
                    emptyCount++;
                }
            }
        }
        
        // Call the helper function to find all unique paths
        dfs(grid, startX, startY, emptyCount);
        
        return numOfPaths;
    }
    
    private void dfs(int[][] grid, int x, int y, int emptyCount) {
        // Base Cases:
        // If current cell is out of grid bounds, return
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length)
            return;
        
        // If current cell is obstacle, return
        if (grid[x][y] == -1)
            return;
        
        // If current cell is already visited, return
        if (grid[x][y] == 3)
            return;
        
        // If current cell reaches the end cell and all empty cells are visited, increment the count of unique paths
        if (grid[x][y] == 2 && emptyCount == 0) {
            numOfPaths++;
            return;
        }
        
        // Mark the current cell as visited
        grid[x][y] = 3;
        
        // Recursive calls in all four directions: up, down, left, right
        dfs(grid, x + 1, y, emptyCount - 1); // Move down
        dfs(grid, x - 1, y, emptyCount - 1); // Move up
        dfs(grid, x, y + 1, emptyCount - 1); // Move right
        dfs(grid, x, y - 1, emptyCount - 1); // Move left
        
        // Backtrack by marking the current cell as unvisited
        grid[x][y] = 0;
    }
}

1. Algorithm Description: To solve the "Unique Paths III" problem, we can use a Depth-First Search (DFS) approach.

The idea behind the DFS approach is to traverse through each cell in the grid and explore all possible paths from the start cell to the end cell. We use a recursive function, dfs, to perform the DFS traversal.

In the uniquePathsIII function, we first find the start cell and count the number of empty cells (excluding the start cell). Then, we call the dfs function to find all unique paths.

The dfs function takes the current cell's coordinates (x, y) and the count of empty cells as parameters. It uses several base cases to handle different scenarios, such as reaching an obstacle or already visited cell.

If the current cell reaches the end cell and all empty cells are visited, we increment the count of unique paths. Otherwise, we mark the current cell as visited and make recursive calls to explore paths in all four directions: up, down, left, and right.

After making the recursive calls, we backtrack by marking the current cell as unvisited so that it can be explored in other paths.

During the interview process, it is important to understand the problem statement and constraints. You should analyze the problem and come up with an efficient approach. The DFS approach described above is an optimized solution that can handle large grid sizes efficiently.

In the interview, you can explain the problem, discuss possible approaches, and provide the optimized solution with detailed comments. You can also discuss the time and space complexity of the algorithm and any potential optimizations or alternative approaches.