Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

//DFS, time:O(n^2), space:O(1)
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        subsetsHelper(nums, ans, new ArrayList<Integer>(), 0);
        return ans;
    }
    public void subsetsHelper(int[] nums, List<List<Integer>> ans,                                 List<Integer> list, int start) {
        ans.add(new ArrayList<Integer>(list));
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsHelper(nums, ans, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}


/*
bfs:
First, adding an empty list to the ans, then iterate the input array, each time adding the number to all the existed subsets. The new subsets and the previous subsets together make up the new ans. 

time:O(n^2), space:O(1)
*/

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        List<Integer> list = new ArrayList<>();
        ans.add(list);
        for (int i = 0; i < nums.length; i++) {
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                list = new ArrayList<>(ans.get(j));
                list.add(nums[i]);
                ans.add(list);
            }
        }
        return ans;
    }
}

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *        label = x; 
 *        neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */

/*
Use Queue to implement BFS and use HashMap to deep clone every graph node and connect their neighbors.

time:O(V+E), space:O(V), E is the number of neighbors, V is the number of nodes.
*/

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                }
                map.get(curr).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}


//DFS, time:O(V+E), space:O(V)
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        return deepClone(map, node);
    }
    public UndirectedGraphNode deepClone(Map<UndirectedGraphNode,                                              UndirectedGraphNode> map, UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }
        map.put(node, new UndirectedGraphNode(node.label)); 
        for (UndirectedGraphNode neighbor : node.neighbors) {
            map.get(node).neighbors.add(deepClone(map, neighbor));
        }
        return map.get(node);
    }

}

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

/*
BFS traversal, 
time:O(n), space:O(n)
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

/*

When find one land, increment the number of lands, then use DFS/BFS to find all the adjacent lands. In order to avoid duplicate, set each land just found to be water, like set '1' to '0'.

*/

//DFS, time:O(m*n), space:O(1)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                dfs(grid, i, j);

            }

        }

        return count;

    }

    public void dfs(char[][] grid, int i, int j) {

        if (i < 0 || i >= grid.length || 

            j < 0 || j >= grid[0].length) {

            return;

        }

        if (grid[i][j] == '1') {

            grid[i][j] = '0';

            dfs(grid, i + 1, j);

            dfs(grid, i, j + 1);

            dfs(grid, i - 1, j);

            dfs(grid, i, j - 1);

        }

    }

}

//BFS, time:O(m*n), space:O(m*n)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                bfs(grid, i, j);

            }

        }

        return count;

    }

    public void bfs(char[][] grid, int i, int j) {

        int m = grid.length;

        int n = grid[0].length;

        int[] dx = {1, 0, -1, 0};

        int[] dy = {0, 1, 0, -1};

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(i * n + j);

        grid[i][j] = '0';

        while (!queue.isEmpty()) {

            int index = queue.poll();

            for (int k = 0; k < 4; k++) {

                int nx = index / n + dx[k];

                int ny = index % n + dy[k];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {

                    continue;

                }

                if (grid[nx][ny] == '0') {

                    continue;

                }

                queue.offer(nx * n + ny);

                grid[nx][ny] = '0';

            }

        }

    }

}

Maze

Given a matrix filled with '1's and '0's and only one '9'. Suppose 0 means one can not pass through it and 1 means one can pass. If one can only start at point (0,0), can s/he arrives at the point filled with '9'? (One can only move either up or down or left or right at any point in time.) 

/*
This problem is similar to "Number of Islands", we can use either DFS or BFS to traverse each point start from (0,0) until arriving at 9 or the next paths all being blocked. 
*/

/*
In BFS, there is a tricky way to convert the 2D coordinate into 1D number. And use dx = {1, 0, -1, 0},dy = {0, 1, 0, -1} in the code to avoid redundancy.

BFS: time:O(n^2), space:O(n^2)
*/

import java.util.*;

public class Solution {
    public static int Maze(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || 
            matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        if (matrix[0][0] == 0) {
            return 0;
        }
        if (matrix[0][0] == 9) {
            return 1;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        matrix[0][0] = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            int x = tmp / n;
            int y = tmp % n;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (matrix[nx][ny] == 0) {
                    continue;
                }
                if (matrix[nx][ny] == 9) {
                    return 1;
                }
                queue.add(nx * n + ny);
                matrix[nx][ny] = 0;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};
        int res = Maze(matrix);
        System.out.print(res);
    }

}

//DFS: time:O(n^2), space:O(1)

import java.util.*;

public class Solution {

    public static int Maze(int[][] matrix) {

        if (matrix == null || matrix[0] == null) {

            return 0;

        }

        return dfs(matrix, 0, 0);

    }

    public static int dfs(int[][] matrix, int x, int y) {

        if (x < 0 || x >= matrix.length || 

            y < 0 || y >= matrix[0].length) {

            return 0;

        }

        if (matrix[x][y] == 9) {

            return 1;

        }

        if (matrix[x][y] == 1) {

            matrix[x][y] = 0;

            if (dfs(matrix, x + 1, y) == 1 || 

                dfs(matrix, x, y + 1) == 1 ||

                dfs(matrix, x - 1, y) == 1 || 

                dfs(matrix, x, y - 1) == 1) {

                return 1;

            };

        }

        return 0;

    }

    public static void main(String[] args) {

        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};

        int res = Maze(matrix);

        System.out.print(res);

    }

}

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].


/*
The problem reduces to find a topological sort order of the courses. If a node has incoming edges, it has prerequisites. Therefore, the first few in the order must be those with no prerequisites, i.e. no incoming edges. Notice, if there is a cycle in the graph, it means it is impossible to finish all the courses.

time:O(n), space:O(n)
*/

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Integer> inMap = countInlinks(prerequisites);
        Map<Integer, ArrayList<Integer>> outMap =                                                 initNeighbors(prerequisites);
        return findOrderByBFS(numCourses, inMap, outMap);
    }
    public Map<Integer, Integer> countInlinks(int[][] pre) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] pair : pre) {
            if (!map.containsKey(pair[0])) {
                map.put(pair[0], 1);
            } else {
                map.put(pair[0], map.get(pair[0]) + 1);
            }
        }
        return map;
    }
    public Map<Integer, ArrayList<Integer>> initNeighbors(int[][]                                                             pre) {
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int[] pair : pre) {
            if (!map.containsKey(pair[1])) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(pair[0]);
                map.put(pair[1], list);
            } else {
                map.get(pair[1]).add(pair[0]);
            }
        }
        return map;
    }
    public int[] findOrderByBFS(int numCourses, Map<Integer,                   Integer> inMap, Map<Integer, ArrayList<Integer>> outMap) {
        int[] ans = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();
        int index = 0;
        for (int course = 0; course < numCourses; course++) {
            if (!inMap.containsKey(course)) {
                ans[index++] = course;
                queue.offer(course);
            }
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            if (!outMap.containsKey(course)) {
                continue;
            }
            for (Integer i : outMap.get(course)) {
             inMap.put(i, inMap.get(i) - 1);
                if (inMap.get(i) == 0) {
                    ans[index++] = i;
                    queue.offer(i);
                }
            }
        }
        return index == numCourses ? ans : new int[0];
    }
}

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

/*
For it wants us to return all possible letter combinations, it is a problem of search. We can use DFS or BFS to solve it.
*/

//DFS: time:O(2^n), space:O(1)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] map = {"", "", "abc", "def", "ghi", "jkl", 
                        "mno", "pqrs", "tuv", "wxyz"};
        helper(map, digits, ans, "");
        return ans;
    }
    public void helper(String[] map, String digits, 
                       List<String> ans, String str) {
        if (str.length() == digits.length()) {
            ans.add(str);
            return;
        }
        int num = digits.charAt(str.length()) - '0';
        for (char ch : map[num].toCharArray()) {
            helper(map, digits, ans, str + ch);
        }
    }
}


//BFS: time:O(2^n), space:O(2^n)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] map = {"", "", "abc", "def", "ghi", 
                        "jkl", "mno", "pqrs", "tuv", "wxyz"};
        Queue<String> queue = new LinkedList<>();
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            while (queue.peek().length() == i) {
                String str = queue.poll();
                for (char ch : map[num].toCharArray()) {
                    queue.offer(str + ch);
                }
            }
        }
        while (!queue.isEmpty()) {
            ans.add(queue.poll());
        }
        return ans;
    }

}