40. Combination Sum II

五刷 06/2022

Version #1 DFS with Backtracking

Time O(N * 2^N) -> 2^N to exhaust all combinations, and N to deep copy the path list

Space O(N) -> depth of the tree

Runtime: 5 ms, faster than 70.80% of Java online submissions for Combination Sum II.

Memory Usage: 42.3 MB, less than 97.79% of Java online submissions for Combination Sum II.

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();

        if (candidates == null || candidates.length == 0) {

            return result;

        }

        // sort in order to guarantee that the same number won't be added multiple times at the same layer

        Arrays.sort(candidates);

        dfs(candidates, target, 0, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {

        if (target == 0) {

            result.add(new ArrayList<>(path));

            return;

        }

        if (target < 0) {

            return;

        }

        for (int i = startIndex; i < candidates.length; i++) {

            if (i != startIndex && candidates[i] == candidates[i - 1]) {

                continue;

            }

            path.add(candidates[i]);

            dfs(candidates, target - candidates[i], i + 1, path, result);

            path.remove(path.size() - 1);

        }

    }

}

四刷

05/21/2021

一遍就过了

Runtime: 2 ms, faster than 98.71% of Java online submissions for Combination Sum II.

Memory Usage: 39.3 MB, less than 49.53% of Java online submissions for Combination Sum II.

Time complexity O(2^n)

Space complexity O(n) Memory Heap size

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        // 1, 2, 2, 6, 7, 10 if we are going to use the duplicate number, then always start with the first

        List<List<Integer>> result = new ArrayList<>();

        helper(0, candidates, target, new ArrayList<>(), result);

        return result;

    }

    

    private void helper(int index, int[] candidates, int target, List<Integer> path, List<List<Integer>> result) {

        if (target == 0) {

            result.add(new ArrayList<>(path));

            return;

        }

        if (index == candidates.length) {

            return;

        }

        for (int i = index; i < candidates.length; i++) {

            if (candidates[i] > target) {

                break;

            }

            if (i != index && candidates[i] == candidates[i - 1]) {

                continue;

            }

            path.add(candidates[i]);

            helper(i + 1, candidates, target - candidates[i], path, result);

            path.remove(path.size() - 1);

        }

    }

}

三刷

Time Complexity O(2^n) -> generate all subsets

Space Complexity Heap Size -> Tree Height  -> O(n)

index == start

98.44 %

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();

        if (candidates == null || candidates.length == 0 || target <= 0) return result;

        Arrays.sort(candidates);

        helper(0, candidates, target, new ArrayList<>(), result);

        return result;

    }

    // Each layer we subtract a number from remaining target value

    // When we see duplicate value, we make sure always get the 1st element at that layer to avoid duplication

    private void helper(int start, int[] candidates, int target, List<Integer> path, List<List<Integer>> result) {

        if (target == 0) {

            result.add(new ArrayList<>(path));

            return;

        }

        for (int index = start; index < candidates.length && candidates[index] <= target; index++) {

            if (index == start || candidates[index] != candidates[index - 1]) {

                path.add(candidates[index]);

                helper(index + 1, candidates, target - candidates[index], path, result);

                path.remove(path.size() - 1);

            }

        }

    }

}

Note:

The variable"i" means represents that we are choosing the ith number in the current layer.

If "i" does not equal to the startIndex of the current layer, we can know that we have skipped the previous number. In this situation, if the current number equals to its previous number, we can know that we are choosing the second number between the 2 same ones, which is not satisfying our requirement. So 1st we'll check (index != startIndex), 2nd we'll check (nums[i] == nums[i - 1]). If both of them are true, we'll need to do "continue" to skip the current i.

二刷

这道题是39的follow up 第五遍了还是index有问题。。。我还能说啥。。。

84.95 %

/*

No one number can be choose twice

sort first

if there's equal numbers e.g.  1 2 2 3

we want to make 1 + 2 + 2 eligible and avoid 1 + 2(1) and 1 + 2(2) 

so at the same layer, we always choose the 1st number of the equal ones

*/

public class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();

        if (candidates == null || candidates.length == 0 || target <= 0) return result;

        Arrays.sort(candidates);

        dfs(candidates, target, 0, new ArrayList<Integer>(), result);

        return result;

    }

    private void dfs(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {

        if (target == 0) {

            result.add(new ArrayList<Integer>(path));

            return;

        }

        int curr = 0;

        for (int i = startIndex; i < candidates.length; i++) {

            curr = candidates[i];

            if (curr > target) break;

            if (i != startIndex && curr == candidates[i - 1]) continue;

            path.add(curr);

            dfs(candidates, target - curr, i + 1, path, result);

            path.remove(path.size() - 1);

        }

    }

}

一刷

 78.25%

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0 || target <= 0) return result;
        Arrays.sort(candidates);
        helper(candidates, target, 0, new ArrayList<Integer>(), result);
        return result;
    }

    public void helper(int[] candidates, int target, int startIndex, List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for (int index = startIndex; index < candidates.length; index++) {
            if (candidates[index] > target) return;
            if (index != startIndex && candidates[index] == candidates[index - 1]) continue;
            path.add(candidates[index]);
            helper(candidates, target - candidates[index], index + 1, path, result);
            path.remove(path.size() - 1);
        }
   
    }

}

Build Post Office II

//[TODO]
In this solution, I have made the same mistake as what I made in the last question. While I am iterating through the whole matrix, I should record both the list of HOUSEs and EMPTYs.

class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Solution {
    /**
     * @param grid a 2D grid
     * @return an integer
     */
    public int WALL = 2;
    public int HOUSE = 1;
    public int EMPTY = 0;
    public int[] dX = {1, 0, -1, 0};
    public int[] dY = {0, 1, 0, -1};
    public int shortestDistance(int[][] grid) {
        // Write your code here
        int[][] distanceFromHouses = new int[grid.length][grid[0].length];
        int[][] visitedCount = new int[grid.length][grid[0].length];
        ArrayList<Point> houses = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == HOUSE) {
                    houses.add(new Point(i, j));
                }
            }
        }
        for (Point house : houses) {
            bfs(house, grid, distanceFromHouses, visitedCount);
        }
        int sum = Integer.MAX_VALUE;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == EMPTY) {
                    //System.out.println(visitedCount[i][j] + " " + distanceFromHouses[i][j]);
                    if (visitedCount[i][j] == houses.size()) {
                        sum = Math.min(distanceFromHouses[i][j], sum);
                    }
                }
            }
        }
        if (sum == Integer.MAX_VALUE) {
            return -1;
        } else {
            return sum;
        }
    }
   
    public void bfs(Point start, int[][] grid, int[][] distanceFromHouses, int[][] visitedCount) {
       
        Queue<Point> que = new LinkedList<>();
        que.add(start);
        int distance = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        while (!que.isEmpty()) {
            distance++;
            int size = que.size();
            for (int k = 0; k < size; k++) {
                Point curr = que.poll();
                //neighbors
                for (int i = 0; i < 4; i++) {
                    int x = curr.x + dX[i];
                    int y = curr.y + dY[i];
                    if (isValid(x, y, grid) && !visited[x][y]) {
                        distanceFromHouses[x][y] += distance;
                        visitedCount[x][y]++;
                        visited[x][y] = true;
                        que.add(new Point(x, y));
                    }
                }
            }
           
        }
    }
   
    public boolean isValid(int x, int y, int[][] grid) {
        if (x < 0 || x >= grid.length) {
            return false;
        }
        if (y < 0 || y >= grid[0].length) {
            return false;
        }
        return grid[x][y] == EMPTY;
    }
   
}

Zombie in Matrix

In the 1st version of my solution, I traversed the matrix twice. The first traversal is to get all the zombies of the initial state, the second traversal is to check if there are any people left in the matrix.
This version is not optimal since it is wasteful to traverse the matrix twice.

class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int WALL = 2;
    public int ZOMBIE = 1;
    public int PEOPLE = 0;
    public int[] dX = {1, 0, -1, 0};
    public int[] dY = {0, 1, 0, -1};
    public int zombie(int[][] grid) {
        // Write your code here
        int days = 0;
        if (grid == null) {
            return days;
        }
        if (grid.length == 0 || grid[0].length == 0) {
            return days;
        }
        Queue<Point> que = new LinkedList<Point>();
       
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == ZOMBIE) {
                    que.offer(new Point(x, y));
                }
            }
        }
       
        while(!que.isEmpty()) {
            days++;
            int size = que.size();
            for (int day = 0; day < size; day++) {
                Point curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int neighborX = curr.x + dX[i];
                    int neighborY = curr.y + dY[i];
                    Point neighbor = new Point(neighborX, neighborY);
                    if (isValid(grid, neighbor)) {
                        grid[neighborX][neighborY] = ZOMBIE;
                        que.add(neighbor);
                    }
                }
               
            }
        }
       
       
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == PEOPLE) {
                    return -1;
                }
            }
           
        }
        return days - 1;
    }
 
    public boolean isValid(int[][] grid, Point point) {
        if (point.x < 0 || point.x >= grid.length) {
            return false;
        }
        if (point.y < 0 || point.y >= grid[0].length) {
            return false;
        }
        return grid[point.x][point.y] == PEOPLE;
    }
}


-----------------------------------------------------
Improved version.
Count the number of people in the first traversal. Return when the number of people is reduced to zero.

class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int WALL = 2;
    public int ZOMBIE = 1;
    public int PEOPLE = 0;
    public int[] dX = {1, 0, -1, 0};
    public int[] dY = {0, 1, 0, -1};
    public int zombie(int[][] grid) {
        // Write your code here
        int days = 0;
        int people = 0;
        if (grid == null) {
            return days;
        }
        if (grid.length == 0 || grid[0].length == 0) {
            return days;
        }
        Queue<Point> que = new LinkedList<Point>();
       
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == ZOMBIE) {
                    que.offer(new Point(x, y));
                }
                if (grid[x][y] == PEOPLE) {
                    people++;
                }
            }
        }
       
        while(!que.isEmpty()) {
            days++;
            int size = que.size();
            for (int day = 0; day < size; day++) {
                Point curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int neighborX = curr.x + dX[i];
                    int neighborY = curr.y + dY[i];
                    Point neighbor = new Point(neighborX, neighborY);
                    if (isValid(grid, neighbor)) {
                        grid[neighborX][neighborY] = ZOMBIE;
                        people--;
                        if (people == 0) {
                            return days;
                        }
                        que.add(neighbor);
                    }
                }
               
            }
        }
       
        return -1;
    }
 
    public boolean isValid(int[][] grid, Point point) {
        if (point.x < 0 || point.x >= grid.length) {
            return false;
        }
        if (point.y < 0 || point.y >= grid[0].length) {
            return false;
        }
        return grid[point.x][point.y] == PEOPLE;
    }
}

549. Binary Tree Longest Consecutive Sequence II

二刷 08/2022

Version #1 DFS

Time O(N)

Space O(N)

Runtime: 2 ms, faster than 50.69% of Java online submissions for Binary Tree Longest Consecutive Sequence II.

Memory Usage: 45.1 MB, less than 21.33% of Java online submissions for Binary Tree Longest Consecutive Sequence II.

class Solution {

    public int longestConsecutive(TreeNode root) {

        int[] max = new int[1];

        dfs(root, max);

        return max[0];

    }

    

    // returns the longest increasing/decreasing consecutive sequence

    private int[] dfs(TreeNode node, int[] max) {

        if (node == null) {

            return new int[]{0, 0};

        }

        int[] left = dfs(node.left, max);

        int[] right = dfs(node.right, max);

        int[] curr = new int[]{1, 1};

        if (node.left != null) {

            if (node.left.val == node.val - 1) {

                curr[0] = 1 + left[0];

            }

            if (node.left.val == node.val + 1) {

                curr[1] = 1 + left[1];

            }

        }

        if (node.right != null) {

            if (node.right.val == node.val - 1) {

                curr[0] = Math.max(curr[0], 1 + right[0]);

            }

            if (node.right.val == node.val + 1) {

                curr[1] = Math.max(curr[1], 1 + right[1]);

            }

        }

        max[0] = Math.max(max[0], curr[0] + curr[1] - 1);

        return curr;

    }

}

一刷

FLAW:
We don't have to distinguish the int leftAsc &rightAsc, leftDesc &rightDesc. Both of those pairs can be merged into maxAsc and maxDesc, and we can simply calculate the temp max path by maxAsc + 1 + maxDesc. In this way, the code will be neater.


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class ResultType {
    public int maxAsc;
    public int maxDesc;
    public ResultType(int maxAsc, int maxDesc) {
        this.maxAsc = maxAsc;
        this.maxDesc = maxDesc;
    }
}

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the length of the longest consecutive sequence path
     */
    int max = 0;
   
    public int longestConsecutive2(TreeNode root) {
        // Write your code here
     
        if (root == null) {
            return max;
        }
        helper(root);
        return max;
    }
 
    public ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, 0);
        }
     
        int maxAsc = 1;
        int maxDesc = 1;
     
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        //The root is not included
        int leftAsc = 0;
        int leftDesc = 0;
        int rightAsc = 0;
        int rightDesc = 0;
     
        if (root.left != null) {
            //descending up -> down
            if (root.val == root.left.val + 1) {
                leftDesc = left.maxDesc;
            } else if (root.val == root.left.val - 1) {
                //ascending up -> down
                leftAsc = left.maxAsc;
            }
        }
     
        if (root.right != null) {
            if (root.val == root.right.val + 1) {
                //descending up -> down
                rightDesc = right.maxDesc;
            } else if (root.val == root.right.val - 1) {
                //ascending up -> down
                rightAsc = right.maxAsc;
            }
        }
     
        int tempPath = Math.max(leftAsc + 1 + rightDesc, rightAsc + 1 + leftDesc);
        max = Math.max(max, tempPath);
     
        maxAsc = Math.max(maxAsc, leftAsc + 1);
        maxAsc = Math.max(maxAsc, rightAsc + 1);
        maxDesc = Math.max(maxDesc, leftDesc + 1);
        maxDesc = Math.max(maxDesc, rightDesc + 1);
     
        max = Math.max(max, maxAsc);
        max = Math.max(max, maxDesc);
        return new ResultType(maxAsc, maxDesc);
        //ResultType result = new ResultType();
     
    }
}