Tree/Graph DP

1. Binary Tree Maximum Path Sum

  1. Problem Description:

The problem "Binary Tree Maximum Path Sum" asks us to find the maximum path sum in a binary tree. In other words, we need to find the path in the binary tree with the maximum sum of node values.

LeetCode Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/

  1. Optimized Java Code:

class Solution {
    // Global variable to store the maximum path sum
    int maxPathSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        // Call the helper function to start the recursion
        maxGain(root);
        return maxPathSum;
    }
    
    private int maxGain(TreeNode node) {
        // Base case: if node is null, return 0
        if (node == null) {
            return 0;
        }
        
        // Recursively find the maximum gain of left and right subtrees
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // Calculate the maximum sum including the current node
        int currentSum = node.val + leftGain + rightGain;
        
        // Update the maximum path sum if the current sum is greater
        maxPathSum = Math.max(maxPathSum, currentSum);
        
        // Return the maximum gain of the current node (either left or right + current node)
        return node.val + Math.max(leftGain, rightGain);
    }
}

  1. Algorithm and Approach:

During the interview process, you can follow these steps to tackle the "Binary Tree Maximum Path Sum" problem:

  • We can approach this problem using recursion and divide-and-conquer technique.

  • First, let's define a recursive helper function maxGain that takes a node as input and returns the maximum gain (maximum sum of nodes) that can be obtained from the subtree rooted at that node.

  • The base case for the recursion will be when the node is null. In this case, we return 0.

  • For each node, we calculate the maximum gain of its left and right subtrees by recursively calling the maxGain function.

  • We update a global variable maxPathSum with the maximum sum obtained so far, which will be updated when calculating the maximum sum including the current node.

  • Finally, we return the maximum gain of the current node (either left or right gain + current node value) to the parent node.

  • In the main maxPathSum function, we call the maxGain function on the root of the binary tree to start the recursion.

  • Once the recursion is done, we return the value stored in the maxPathSum variable, which will be the maximum path sum in the binary tree.

  • The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once.

  • The space complexity is O(H), where H is the height of the binary tree. This is because the maximum height of the function call stack during recursion is equal to the height of the binary tree.

2. House Robber III

  1. Problem Description: The problem "House Robber III" on LeetCode asks us to find the maximum amount of money we can rob from a binary tree of houses. Each house contains a certain amount of money, and the constraint is that we cannot rob two adjacent houses (parent and child) on the tree.

Link to the problem on LeetCode: House Robber III

  1. Optimized Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] result = helper(root);
        return Math.max(result[0], result[1]);
    }
    
    private int[] helper(TreeNode node) {
        if (node == null) {
            return new int[2];
        }
        
        int[] left = helper(node.left);
        int[] right = helper(node.right);
        
        int[] result = new int[2];
        // result[0] represents the maximum amount of money that can be robbed if the current node is not robbed
        // result[1] represents the maximum amount of money that can be robbed if the current node is robbed
        
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = node.val + left[0] + right[0];
        
        return result;
    }
}

  1. Algorithm Explanation and Interview Approach: The approach to solving the "House Robber III" problem can be summarized as follows:

  • We need to calculate the maximum amount of money that can be robbed from the binary tree. The constraint is that we cannot rob two adjacent houses.

  • We can solve this problem using a recursive approach.

  • For each node, we need to calculate the maximum amount of money that can be robbed if the node is either robbed or not robbed.

  • We define an array, result[], with two elements:

    • result[0] represents the maximum amount of money that can be robbed if the current node is not robbed.

    • result[1] represents the maximum amount of money that can be robbed if the current node is robbed.

  • For each node, we calculate the maximum amount of money that can be robbed using the following equations:

    • result[0] = max(max(left[0], left[1]) + max(right[0], right[1])) - if the current node is not robbed, we can choose whether to rob its left and right children or not.

    • result[1] = node.val + left[0] + right[0] - if the current node is robbed, we must not rob its left and right children.

  • Finally, we return the maximum of result[0] and result[1] as the answer.

During an interview, it is crucial to understand the problem and its constraints clearly. It is also important to communicate your thought process to the interviewer. Breaking down the problem into smaller subproblems and identifying the optimal substructure can help in devising an efficient solution.

Keep in mind that LeetCode problems might have multiple solutions, and this is just one of them. It is recommended to discuss and explore different approaches and their trade-offs during an interview.

3. Word Break

  1. Problem Description: The problem "Word Break" is stated as follows:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given the string "leetcode" and the dictionary ["leet", "code"], return true because "leetcode" can be segmented as "leet code".

Problem Link: Word Break

  1. Java Code:

import java.util.*;

public class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Create a set to store all the dictionary words for efficient lookup
        Set<String> wordSet = new HashSet<>(wordDict);
        
        // Create a boolean array, dp, to store if a substring from start to i is present in the dictionary
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; // Empty string is always present in the dictionary
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // Check if the substring from j to i is present in the dictionary
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

  1. Algorithm Explanation and Approach:

  • We are given a string s and a list of words in wordDict. Our goal is to check if we can break the string s into words present in the wordDict.

  • To solve this problem, we can use the dynamic programming approach. We create a boolean array dp of length s.length() + 1. Each element dp[i] represents if the substring from the start of the string to index i is present in the wordDict.

  • Initially, we set dp[0] = true to represent an empty string, which is always present in the dictionary.

  • For every index i from 1 to s.length(), we iterate through all indices j from 0 to i-1. We check if the substring from j to i is present in the wordDict and if the substring from the start to index j is also present in the wordDict.

  • If both conditions are true, we set dp[i] = true and break the loop.

  • Finally, we return dp[s.length()] which represents if the string s can be broken into words present in the wordDict.

  • This algorithm has a time complexity of O(n^2), where n is the length of the string s, as we are using nested loops to iterate through all possible substrings.

4. Word Break II

  1. Problem Description and Link: The problem "Word Break II" on LeetCode asks you to find all possible word break combinations for a given string s using a given word dictionary. The link to the problem is: https://leetcode.com/problems/word-break-ii/

  2. Optimized Java Code for Word Break II:

import java.util.*;

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<String, List<String>> memo = new HashMap<>();
        return wordBreakHelper(s, wordDict, memo);
    }
    
    private List<String> wordBreakHelper(String s, List<String> wordDict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        
        List<String> result = new ArrayList<>();
        
        if (s.length() == 0) {
            result.add("");
            return result;
        }
        
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                String subString = s.substring(word.length());
                List<String> subResult = wordBreakHelper(subString, wordDict, memo);
                
                for (String sub : subResult) {
                    String space = sub.isEmpty() ? "" : " ";
                    result.add(word + space + sub);
                }
            }
        }
        
        memo.put(s, result);
        return result;
    }
}

  1. Description of the Algorithm and Approach: In this problem, we need to find all possible word break combinations for a given string. This can be solved using a recursive approach with memoization.

The main idea is to divide the input string into two parts: a prefix and a suffix. If the prefix exists in the word dictionary, we recursively find all possible word break combinations for the suffix. The final result will be the combination of the prefix and each possible combination for the suffix.

To optimize the solution, we use memoization. We maintain a map called memo to store the computed results for each string. This avoids redundant calculations and improves the overall efficiency.

The wordBreakHelper function takes the input string s, the word dictionary wordDict, and the memo map as parameters. It first checks if the result for the current string s is already present in the memo. If it is, we return the stored result.

Next, we check if the string s is empty. If it is, we add an empty string to the result list and return it. This handles the base case where the complete string has been broken down into words.

For each word in the word dictionary, we check if s starts with that word. If it does, we extract the substring after that word and recursively find all possible word break combinations for the remaining suffix. We add the current word and each suffix combination to the result list.

Finally, we store the result for the current string s in the memo and return it.

During an interview, it's important to understand and explain the concept of recursion, backtracking, and memoization. Additionally, discussing the time and space complexities of the solution helps demonstrate a solid understanding of the problem and its solution.

5. Number of Binary Trees

  1. Problem Description:

The problem is called "Number of Binary Trees" and can be found on Leetcode at the following link: https://leetcode.com/problems/unique-binary-search-trees/

Given an integer n, return the number of structurally unique BST's (binary search trees) that can be formed with nodes labeled from 1 to n.

  1. Optimized Java Code:

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

  1. Detailed Description and Algorithm:

In this problem, we need to find the number of structurally unique binary search trees that can be formed with nodes labeled from 1 to n.

One way to approach this problem is by using dynamic programming. We can define an array dp of size n+1, where dp[i] represents the number of unique BSTs that can be formed using i nodes.

To find dp[i], we can iterate over all possible values of j from 1 to i (representing the root of the binary search tree), and calculate the number of unique BSTs that can be formed with j-1 nodes on the left subtree and i-j nodes on the right subtree.

The total number of unique BSTs that can be formed with i nodes is the sum of these values for all possible values of j.

To optimize this solution, we can use an array dp to store the number of unique BSTs for each number of nodes. We initialize dp[0] and dp[1] to 1 since there is only one unique BST with 0 or 1 node.

Then, we iterate from 2 to n and for each i, we iterate from 1 to i (j), calculate dp[i] as the sum of dp[j-1] * dp[i-j]. This represents the number of unique BSTs we can form with i nodes.

Finally, we return dp[n] which represents the number of unique BSTs that can be formed with n nodes.

This optimized solution has a time complexity of O(n^2) and a space complexity of O(n), where n is the given input.

PreviousString DPNextOptimization Problems

Last updated