Divide conquer idea with memorization, 3ms, beats 83.24%


  • 0
    Z

    The basic idea is very similar to lots of solutions here but I use a hashmap to record the result that I have already got so that it avoids to search the same sub-results multiple times.

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            if (n <= 0) {
                return new ArrayList<TreeNode>();
            }
            Map<String, List<TreeNode>> map = new HashMap<String, List<TreeNode>>();
            return helper(map, 1, n);
        }
        
        private List<TreeNode> helper(Map<String, List<TreeNode>> map, int start, int end) {
            String s = String.valueOf(start + " " + end);
            if (map.containsKey(s)) {
                return map.get(s);
            } 
            
            List<TreeNode> result = new ArrayList<TreeNode>();
            if (start > end) {
                result.add(null);
                return result;
            }
            
            for (int i = start; i <= end; i++) {
                List<TreeNode> left = helper(map, start, i - 1);
                List<TreeNode> right = helper(map, i + 1, end);
                for (TreeNode l: left) {
                    for (TreeNode r: right) {
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;
                        result.add(root);
                    }
                }
            }
            
            map.put(s, result);
            return result;
        }
    }
    

  • 0
    S

    what will be the time complexity of such a solution ?


  • 0
    Z

    hi @shilpa6, I think with memorization, the time complexity is O(n ^ 2), because it is the number of ways of two-number-combination. For example, we have pair(1, 1), pair(1, 2), pair(1, 3)....pair(1, n), and we have pair(2, 2), pair(2, 3), pair(2, 4)...pair(2, n) and so on.

    Without memorization, the time complexity will be exponential because we have recursively call the helper function, and we do not avoid searching the same subproblems.

    Hope that is clear to you. Thanks.


  • 0
    S

    Hi @zfuuuuu , Thanks a lot for the explanation! I think it will still add another n^2 to the merge of 2 pairs where we need put traverse through the left and right results of every pair. Like for a pair(1,5) we will have to combine results from pair(1,3) and pair(4,5). This can add an additional n^2 ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.