BFS

BFS好题选编

301. Remove Invalid Parentheses

经测试，BFS比backtracking快得多！

注意到题目中要求最少删除，这样的描述正是广度优先搜索算法应用的场景，并且题目也要求我们输出所有的结果。我们在进行广度优先搜索时每一轮删除字符串中的 1 个括号，直到出现合法匹配的字符串为止，此时进行轮转的次数即为最少需要删除括号的个数。

我们进行广度优先搜索时，每次保存上一轮搜索的结果，然后对上一轮已经保存的结果中的每一个字符串尝试所有可能的删除一个括号的方法，然后将保存的结果进行下一轮搜索。在保存结果时，我们可以利用哈希表对上一轮生成的结果去重，从而提高效率。

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<String>();
        Set<String> currSet = new HashSet<String>();

        currSet.add(s);
        while (true) {
            for (String str : currSet) {
                if (isValid(str)) {
                    ans.add(str);
                }
            }
            if (ans.size() > 0) {	//直到第一次出现合法匹配的字符串，此时删除次数必然最少
                return ans;
            }
            Set<String> nextSet = new HashSet<String>();
            for (String str : currSet) {
                for (int i = 0; i < str.length(); i ++) {
                    if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {// 进一步优化运行速度，去掉也可以; 只需考虑删除相邻两个相同字符中的一个即可，不必重复考虑
                        continue;
                    }
                    if (str.charAt(i) == '(' || str.charAt(i) == ')') {
                        nextSet.add(str.substring(0, i) + str.substring(i + 1));
                    }
                }
            }
            currSet = nextSet;
        }
    }

    private boolean isValid(String str) {	//判断valid无需分别计数left和right
        char[] ss = str.toCharArray();
        int count = 0;

        for (char c : ss) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
                if (count < 0) {
                    return false;
                }
            }
        }

        return count == 0;
    }
}

133. Clone Graph

Map<Node,Node> map;
public Node cloneGraph(Node node) {
    if(node==null){
        return null;
    }
    map=new HashMap<>();
    Deque<Node> queue=new LinkedList<>();   //队中放入老节点
    queue.offer(node);
    map.put(node,new Node(node.val,new ArrayList<>()));
    //直到队空
    while(!queue.isEmpty()){
        Node cur=queue.poll();
        for (Node next : cur.neighbors) {
            if(!map.containsKey(next)){	//第一次访问到该老节点，则入队，并复制
                queue.offer(next);
                map.put(next,new Node(next.val,new ArrayList<>()));
            }
            map.get(cur).neighbors.add(map.get(next));

        }
    }
    return map.get(node);
}

Node[] clone;
public Node cloneGraph(Node node) {
    if(node==null){
        return null;
    }
    Deque<Node> queue=new LinkedList<>();
    clone=new Node[101];
    queue.offer(node);
    while(!queue.isEmpty()){
        Node cur=queue.poll();
        int val=cur.val;
        if(clone[val]==null){
            Node newNode=new Node(val);
            clone[val]=newNode;
        }
        for (Node next : cur.neighbors) {
            if(clone[next.val]==null){
                queue.offer(next);
                Node newNext=new Node(next.val);
                clone[next.val]=newNext;
            }
            clone[val].neighbors.add(clone[next.val]);
        }
    }
    return clone[1];

269. Alien Dictionary

拓扑排序，用dfs需要三要素+后序遍历逆序，用bfs结果无需逆序，也需三要素：

• 入度数组
• 出队计数器count
• 当前入度为0的queue

public String alienOrder(String[] words) {
    Set<Character> set=new HashSet<>();
    Map<Character,List<Character>> graph=new HashMap<>();

    for (String word : words) {
        for (int i = 0; i < word.length(); i++) {
            set.add(word.charAt(i));
        }
    }

    for (int i = 1; i < words.length; i++) {
        String small=words[i-1];
        String big=words[i];
        int len=Math.max(small.length(),big.length());
        for (int j = 0; j < len; j++) {
            if(j==big.length()){    //invalid
                return "";
            }
            if(j==small.length()){
                break;
            }
            if(small.charAt(j)!=big.charAt(j)){
                char from=small.charAt(j);
                char to=big.charAt(j);
                graph.putIfAbsent(from,new ArrayList<>());
                graph.get(from).add(to);
                break;
            }
        }
    }

    StringBuilder sb=new StringBuilder();
    int count=0;
    Deque<Character> queue=new LinkedList<>();
    int[] in=new int[26];
    for (List<Character> tos : graph.values()) {
        for (Character to : tos) {
            in[to-'a']++;
        }
    }
    for (Character c : set) {
        if(in[c-'a']==0){
            queue.offer(c);
        }
    }
    while(!queue.isEmpty()){
        char cur=queue.poll();
        sb.append(cur);
        count++;
        if(graph.containsKey(cur)){
            for (Character next : graph.get(cur)) {
                in[next-'a']--;
                if(in[next-'a']==0){
                    queue.offer(next);
                }
            }
        }
    }
    return count==set.size() ? sb.toString() : "";
}

优化：

public String alienOrder(String[] words) {
    List<Character>[] graph=new List[26];
    Map<Character,Integer> ins=new HashMap<>();
    for (String word : words) {
        for (int i = 0; i < word.length(); i++) {
            ins.put(word.charAt(i),0);
        }
    }
    for (int i = 1; i < words.length; i++) {
        String first=words[i-1];
        String second=words[i];
        int l=Math.max(first.length(),second.length());
        for (int j = 0; j < l; j++) {
            if(j==first.length()){
                break;
            }
            if(j==second.length()){
                return "";
            }
            char a=first.charAt(j);
            char b=second.charAt(j);
            if(a!=b){
                if(graph[a-'a']==null){
                    graph[a-'a']=new ArrayList<>();
                }
                graph[a-'a'].add(b);
                ins.put(b,ins.get(b)+1);
                break;
            }
        }
    }
    StringBuilder sb=new StringBuilder();
    Deque<Character> queue=new LinkedList<>();
    for (Character c : ins.keySet()) {
        if(ins.get(c)==0){
            queue.offer(c);
        }
    }
    while(!queue.isEmpty()){
        char cur=queue.poll();
        sb.append(cur);
        if(graph[cur-'a']!=null){
            for (Character next : graph[cur - 'a']) {
                ins.put(next,ins.get(next)-1);
                if(ins.get(next)==0){
                    queue.offer(next);
                }
            }
        }
    }
    if(sb.length()==ins.size()){
        return sb.toString();
    }
    return "";
}

100. Same Tree

DFS：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p==null && q==null){
        return true;
    }
    if(p==null || q==null){
        return false;
    }
    return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

BFS:

public boolean isSameTree(TreeNode p, TreeNode q) {
    Deque<TreeNode> q1=new LinkedList<>();
    Deque<TreeNode> q2=new LinkedList<>();
    q1.offer(p);
    q2.offer(q);
    while(!q1.isEmpty() && !q2.isEmpty()){
        TreeNode node1=q1.poll();
        TreeNode node2=q2.poll();
        if(node1==null && node2==null){
            continue;
        }
        if(node1==null || node2==null || node1.val!=node2.val){
            return false;
        }
        q1.offer(node1.left);
        q1.offer(node1.right);
        q2.offer(node2.left);
        q2.offer(node2.right);
    }
    return q1.isEmpty() && q2.isEmpty();
}

102. Binary Tree Level Order Traversal

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        List<Integer> list=new ArrayList<>();
        int size=q.size();
        while(size-->0){
            TreeNode node=q.poll();
            list.add(node.val);
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
        res.add(list);
    }
    return res;
}

103. Binary Tree Zigzag Level Order Traversal

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        int size=q.size();
        int idx=res.size();
        LinkedList<Integer> list=new LinkedList<>();
        while(size-->0){
            TreeNode node=q.poll();
            if((idx&1)==0){
                list.add(node.val);
            }else{
                list.addFirst(node.val);
            }
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
        res.add(list);
    }
    return res;
}

104. Maximum Depth of Binary Tree

DFS:

public int maxDepth(TreeNode root) {
    if(root==null){
        return 0;
    }
    if(root.left==null && root.right==null){
        return 1;
    }
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

BFS:

public int maxDepth(TreeNode root) {
    if(root==null){
        return 0;
    }
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    int res=0;
    while(!q.isEmpty()){
        int size=q.size();
        res++;
        while(size-->0){
            TreeNode node=q.poll();
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
    }
    return res;
}

310. Minimum Height Trees

BFS (Time Limit Exceeded)

public class LeetCode310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res=new ArrayList<>();
        int min=Integer.MAX_VALUE;
        int[][] graph=new int[n][n];
        for (int[] edge : edges) {
            int a=edge[0];
            int b=edge[1];
            graph[a][b]=1;
            graph[b][a]=1;
        }
        Deque<Integer> q=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int h=0;
            boolean[] visited=new boolean[n];
            q.clear();
            q.offer(i);
            visited[i]=true;
            while(!q.isEmpty()){
                int size=q.size();
                h++;
                while(size-->0){
                    int root=q.poll();
                    for (int j = 0; j < n; j++) {
                        if(graph[root][j]==1 && !visited[j]){
                            q.offer(j);
                            visited[j]=true;
                        }
                    }
                }
            }
            if(h<=min){
                if(h<min){
                    res.clear();
                    min=h;
                }
                res.add(i);
            }
        }
        return res;
    }
}

Topological sort

• find out the centroids of the circle, i.e. nodes that is close to all the peripheral nodes (leaf nodes)
• For the tree-alike graph, the number of centroids is no more than 2.
  • proved by contradiction
• Given the above intuition, the problem is now reduced down to looking for all the centroid nodes in a tree-alike graph, which in addition are no more than two.
• algorithm: trim out the leaf nodes, layer by layer!!

​

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        // edge cases
        if (n < 2) {
            ArrayList<Integer> centroids = new ArrayList<>();
            for (int i = 0; i < n; i++)
                centroids.add(i);
            return centroids;
        }

        // Build the graph with the adjacency list
        ArrayList<Set<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < n; i++)
            neighbors.add(new HashSet<Integer>());

        for (int[] edge : edges) {
            Integer start = edge[0], end = edge[1];
            neighbors.get(start).add(end);
            neighbors.get(end).add(start);
        }

        // Initialize the first layer of leaves
        ArrayList<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (neighbors.get(i).size() == 1)
                leaves.add(i);

        // Trim the leaves until reaching the centroids
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            ArrayList<Integer> newLeaves = new ArrayList<>();

            // remove the current leaves along with the edges
            for (Integer leaf : leaves) {
                // the only neighbor left for the leaf node
                Integer neighbor = neighbors.get(leaf).iterator().next();
                // remove the edge along with the leaf node
                neighbors.get(neighbor).remove(leaf);
                if (neighbors.get(neighbor).size() == 1)
                    newLeaves.add(neighbor);
            }

            // prepare for the next round
            leaves = newLeaves;
        }

        // The remaining nodes are the centroids of the graph
        return leaves;
    }
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if(n<2){
        List<Integer> res=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(i);
        }
        return res;
    }
    Map<Integer,Set<Integer>> neighbors=new HashMap<>();
    for (int i = 0; i < n; i++) {
        neighbors.put(i,new HashSet<>());
    }
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        neighbors.get(a).add(b);
        neighbors.get(b).add(a);
    }

    List<Integer> leaves=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if(neighbors.get(i).size()==1){
            leaves.add(i);
        }
    }
    int remaining=n;
    while(remaining>2){
        remaining-=leaves.size();
        List<Integer> newLeaves=new ArrayList<>();
        for (Integer leaf : leaves) {
            int neighbor=neighbors.get(leaf).iterator().next();
            neighbors.get(neighbor).remove(leaf);
            if(neighbors.get(neighbor).size()==1){
                newLeaves.add(neighbor);
            }
        }
        leaves=newLeaves;
    }
    return leaves;
}

111. Minimum Depth of Binary Tree

DFS:

public int minDepth(TreeNode root) {
    if(root==null){
        return 0;
    }
    if(root.left==null && root.right==null){
        return 1;
    }
    if(root.left==null){
        return minDepth(root.right)+1;
    }
    if(root.right==null){
        return minDepth(root.left)+1;
    }
    return Math.min(minDepth(root.left),minDepth(root.right))+1;
}

BFS:

public int minDepth(TreeNode root) {
    if(root==null){
        return 0;
    }
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    int res=0;
    while(!q.isEmpty()){
        int size=q.size();
        res++;
        while(size-->0){
            TreeNode node=q.poll();
            if(node.left==null && node.right==null){
                return res;
            }
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
    }
    return -1;
}

112. Path Sum

DFS:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root==null){
        return false;
    }
    if(root.left==null && root.right==null){
        return root.val==targetSum;
    }
    return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}

BFS:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root==null){
        return false;
    }
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        TreeNode node=q.poll();
        if(node.left==null && node.right==null){
            if(node.val==targetSum){
                return true;
            }
        }
        if(node.left!=null){
            node.left.val+=node.val;
            q.offer(node.left);
        }
        if(node.right!=null){
            node.right.val+=node.val;
            q.offer(node.right);
        }
    }
    return false;
}

116. Populating Next Right Pointers in Each Node

O(N) time, O(N) space:

public Node connect(Node root) {
    if(root==null){
        return null;
    }
    Deque<Node> q=new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            Node node=q.poll();
            if(size==0){
                node.next=null;
            }else{
                node.next=q.peek();
            }
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
    }
    return root;
}

O(N) time, O(1) space:

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Start with the root node. There are no next pointers
        // that need to be set up on the first level
        Node leftmost = root;
        
        // Once we reach the final level, we are done
        while (leftmost.left != null) {
            
            // Iterate the "linked list" starting from the head
            // node and using the next pointers, establish the 
            // corresponding links for the next level
            Node head = leftmost;
            
            while (head != null) {
                
                // CONNECTION 1
                head.left.next = head.right;
                
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // Progress along the list (nodes on the current level)
                head = head.next;
            }
            
            // Move onto the next level
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

public Node connect(Node root) {
    if(root==null){
        return null;
    }
    Node cur=root;
    Node leftMost=cur.left;
    while(leftMost!=null){
        Node next=cur.next;
        cur.left.next=cur.right;
        if(next!=null){
            cur.right.next=next.left;
            cur=next;
        }else{
            cur=leftMost;
            leftMost=cur.left;
        }
    }
    return root;
}

127. Word Ladder

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Deque<String> q=new LinkedList<>();
    Set<String> set=new HashSet<>();
    int res=0;
    q.offer(beginWord);
    set.add(beginWord);
    while(!q.isEmpty()){
        int size=q.size();
        res++;
        while(size-->0){
            String cur=q.poll();
            if(cur.equals(endWord)){
                return res;
            }
            for (int i = 0; i < wordList.size(); i++) {
                String s=wordList.get(i);
                if(!set.contains(s) && next(cur,s)){
                    set.add(s);
                    q.offer(s);
                }
            }
        }
    }
    return 0;
}

boolean next(String a, String b){
    int n=a.length();
    int count=0;
    for (int i = 0; i < n; i++) {
        if(a.charAt(i)!=b.charAt(i)){
            count++;
            if(count>1){
                return false;
            }
        }
    }
    return count==1;
}

126. Word Ladder II

easy to count, but how to store the shortest transformation sequeneces?

226. Invert Binary Tree

DFS:

public TreeNode invertTree(TreeNode root) {
    if(root==null){
        return null;
    }
    TreeNode left=root.left;
    root.left=invertTree(root.right);
    root.right=invertTree(left);
    return root;
}

BFS:

public TreeNode invertTree(TreeNode root) {
    if(root==null || root.left==null && root.right==null){
        return root;
    }
    Deque<TreeNode> q=new LinkedList<>();
    invert(root);
    q.addFirst(root.left);
    q.addLast(root.right);
    while(!q.isEmpty()){
        TreeNode l=q.pollFirst();
        TreeNode r=q.pollLast();
        invert(l);
        invert(r);
        if(l!=null && l.right!=null){
            q.offerFirst(l.right);
        }
        if(l!=null && l.left!=null){
            q.offerFirst(l.left);
        }
        if(r!=null && r.left!=null){
            q.offerLast(r.left);
        }
        if(r!=null && r.right!=null){
            q.offerLast(r.right);
        }
    }
    return root;
}

void invert(TreeNode root){
    if(root==null){
        return;
    }
    TreeNode left=root.left;
    root.left=root.right;
    root.right=left;
}

279. Perfect Squares

public int numSquares(int n) {
    Deque<Integer> q=new LinkedList<>();
    q.offer(n);
    int res=0;
    Set<Integer> set=new HashSet<>();
    while(!q.isEmpty()){
        //12           1
        //11,8,3       2
        //10,7,2,4     3
        int size=q.size();
        res++;
        set.clear();
        while(size-->0){
            int cur=q.poll();
            for (int i = 1; i <= cur; i++) {
                int sq=i*i;
                if(sq<=cur){
                    if(sq==cur){
                        return res;
                    }
                    if(!set.contains(cur-sq)){
                        q.offer(cur-sq);
                        set.add(cur-sq);
                    }
                }else{
                    break;
                }
            }
        }
    }
    return -1;
}

286. Walls and Gates

DFS: run time exceeded

public class LeetCode286 {
    int[][] board;
    int row;
    int col;
    public void wallsAndGates(int[][] rooms) {
        board=rooms;
        row=board.length;
        col=board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j]==0){
                    dfs(i,j,i+1,j,1);
                    dfs(i,j,i-1,j,1);
                    dfs(i,j,i,j+1,1);
                    dfs(i,j,i,j-1,1);
                }
            }
        }
    }

    void dfs(int preX, int preY, int i, int j, int dist){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]==-1
                || board[i][j]==0){
            return;
        }
        board[i][j]=Math.min(board[i][j],dist);
        if(preX!=i+1){
            dfs(i,j,i+1,j,dist+1);
        }
        if(preX!=i-1){
            dfs(i,j,i-1,j,dist+1);
        }
        if(preY!=j+1){
            dfs(i,j,i,j+1,dist+1);
        }
        if(preY!=j-1){
            dfs(i,j,i,j-1,dist+1);
        }
    }
}

BFS: O(mn) time and space complexity

private static final int EMPTY = Integer.MAX_VALUE;
private static final int GATE = 0;
private static final List<int[]> DIRECTIONS = Arrays.asList(
        new int[] { 1,  0},
        new int[] {-1,  0},
        new int[] { 0,  1},
        new int[] { 0, -1}
);

public void wallsAndGates(int[][] rooms) {
    int m = rooms.length;
    if (m == 0) return;
    int n = rooms[0].length;
    Queue<int[]> q = new LinkedList<>();
    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (rooms[row][col] == GATE) {
                q.add(new int[] { row, col });
            }
        }
    }
    while (!q.isEmpty()) {
        int[] point = q.poll();
        int row = point[0];
        int col = point[1];
        for (int[] direction : DIRECTIONS) {
            int r = row + direction[0];
            int c = col + direction[1];
            if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != EMPTY) {
                continue;
            }
            rooms[r][c] = rooms[row][col] + 1;
            q.add(new int[] { r, c });
        }
    }
}

302. Smallest Rectangle Enclosing Black Pixels

Approach 1: Naive Linear Search

public int minArea(char[][] image, int x, int y) {
           int top = x, bottom = x;
    int left = y, right = y;
    for (x = 0; x < image.length; ++x) {
        for (y = 0; y < image[0].length; ++y) {
            if (image[x][y] == '1') {
                top = Math.min(top, x);
                bottom = Math.max(bottom, x + 1);
                left = Math.min(left, y);
                right = Math.max(right, y + 1);
            }
        }
    }
    return (right - left) * (bottom - top);
}

Approach 2: BFS/DFS

public int minArea(char[][] image, int x, int y) {
    int row=image.length;
    int col=image[0].length;
    int[] dx={1,-1,0,0};
    int[] dy={0,0,1,-1};
    int minX=x;
    int maxX=x;
    int minY=y;
    int maxY=y;
    Deque<int[]> q=new LinkedList<>();
    q.offer(new int[]{x,y});
    image[x][y]='0';
    while(!q.isEmpty()){
        int[] cur=q.poll();
        for (int k = 0; k < 4; k++) {
            int i=cur[0]+dx[k];
            int j=cur[1]+dy[k];
            if(i<0 || i>=row || j<0 || j>=col || image[i][j]=='0'){
                continue;
            }
            minX=Math.min(minX,i);
            maxX=Math.max(maxX,i);
            minY=Math.min(minY,j);
            maxY=Math.max(maxY,j);
            q.offer(new int[]{i,j});
            image[i][j]='0';
        }
    }
    return (maxX-minX+1)*(maxY-minY+1);
}

317. Shortest Distance from All Buildings

level-ordered BFS

public class LeetCode317 {
    int row;
    int col;
    int[][] grid;
    int[][][] distances;
    int[] dx={1,-1,0,0};
    int[] dy={0,0,1,-1};
    public int shortestDistance(int[][] grid) {
        this.grid=grid;
        row=grid.length;
        col=grid[0].length;
        distances=new int[row][col][2];
        int count=0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    count++;
                    bfs(i,j);
                }
            }
        }
        int res=Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==0 && distances[i][j][1]==count){
                    res=Math.min(res,distances[i][j][0]);
                }
            }
        }
        return res==Integer.MAX_VALUE ? -1 : res;
    }

    void bfs(int i, int j){
        boolean[][] visited=new boolean[row][col];
        Deque<int[]> q=new LinkedList<>();
        q.offer(new int[]{i,j});
        int dist=0;
        while(!q.isEmpty()){
            int size=q.size();
            while(size-->0){
                int[] cur=q.poll();
                int x=cur[0];
                int y=cur[1];
                distances[x][y][0]+=dist;
                distances[x][y][1]++;
                for (int k = 0; k < 4; k++) {
                    int newX=x+dx[k];
                    int newY=y+dy[k];
                    if(newX<0 || newX>=row || newY<0 || newY>=col){
                        continue;
                    }
                    if(!visited[newX][newY] && grid[newX][newY]==0){
                        visited[newX][newY]=true;
                        q.offer(new int[]{newX,newY});
                    }
                }
            }
            dist++;
        }
    }
}

339. Nested List Weight Sum

DFS:

public int depthSum(List<NestedInteger> nestedList) {
     return dfs(nestedList,1);
 }

 int dfs(List<NestedInteger> nestedList, int depth){
     int res=0;
     for(NestedInteger i: nestedList){
         if(i.isInteger()){
             res+=i.getInteger()*depth;
         }else{
             res+=dfs(i.getList(),depth+1);
         }
     }
     return res;
 }

BFS:

public int depthSum(List<NestedInteger> nestedList) {
    int res=0;
    Deque<NestedInteger> q=new LinkedList<>();
    for(NestedInteger i : nestedList){
        q.offer(i);
    }
    int depth=1;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            NestedInteger i=q.poll();
            if(i.isInteger()){
                res+=i.getInteger()*depth;
            }else{
                for(NestedInteger j: i.getList()){
                    q.offer(j);
                }
            }
        }
        depth++;
    }
    return res;
}

365. Water and Jug Problem

https://leetcode.com/problems/water-and-jug-problem/discuss/1055738/VMware-asked-this-in-Interview.-My-BFS-solution-for-interview.

At any state (a,b) of the jugs we can do 6 things.

1. Pour contents of jug1 to jug2. (note that jug1 may still have some water left after pouring water to jug2)
2. Pour contents of jug2 to jug1. (note that jug2 may still have some water left after pouring water to jug1)
3. Empty jug1 completely.
4. Empty jug2 completely.
5. Fill jug1 completely (to its maximum limit)
6. Fill jug2 completely (to its maximum limit)

We are going to keep a note of the already visited states (a,b) of the jugs in a HashSet of string with key being: “a,b” (the capacities of the jugs separated by a comma. This helps us to avoid redundant calculations).

We are going to start with a queue containing only the state (0,0) (both jugs empty) initially. Apply the above 6 operations on that and add those states to the queue if they weren’t already visited. Then simply keep checking whether in any of the states we get the summation of the capacities == z.

If we don’t find any such state. return false.

BFS: Time Limit Exceeded

class State{
       int x,y;
       State(int a, int b){
           this.x=a;
           this.y=b;
       }
   } 
   public boolean canMeasureWater(int x, int y, int z) {
       if(x+y==z) return true;
       if(x+y<z) return false;
       if(x%2==0 && y%2==0 && z%2!=0)//cannot measure odd capacity using even capacity jugs 
           return false;
       
       HashSet<String> visited=new HashSet<>();//state visited hset of jugs
       State start=new State(0,0);
       Queue<State> q=new LinkedList<>();
       q.add(start);
       //run a bfs. don't add already visited states
       while(q.size()>0){
           int n=q.size();
           State curr=q.poll();
           if(curr.x+curr.y==z)
               return true;
           visited.add(curr.x+","+curr.y);
           
           int newY,newX;
           //pour x->y ********************* option 1
           newX=curr.x-Math.min(curr.x,y-curr.y);
           newY=curr.y+Math.min(curr.x,y-curr.y);
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
           
           //pour x<-y ********************* option 2
           newX=curr.x+Math.min(curr.y,x-curr.x);
           newY=curr.y-Math.min(curr.y,x-curr.x);
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
           
           //expty x   ********************* option 3
           newX=0;
           newY=curr.y;//same
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
           
           //empty y   ********************* option 4
           newX=curr.x;//same
           newY=0;
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
           
           //fill x    ********************* option 5
           newX=x;//max capacity
           newY=curr.y;
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
           
           //fill y    ********************* option 6
           newX=curr.x;
           newY=y;//max capacity
           if(!visited.contains(newX+","+newY) )
               q.add(new State(newX,newY));
       }
       return false;
   }

Math

ax + by = k*gcd(a,b)

  public boolean canMeasureWater(int x, int y, int z) {
    //limit brought by the statement that water is finallly in one or both buckets
    if(x + y < z) return false;
    //case x or y is zero
    if( x == z || y == z || x + y == z ) return true;
    
    //get GCD, then we can use the property of Bézout's identity
    return z%GCD(x, y) == 0;
}

public int GCD(int a, int b){
    while(b != 0 ){
        int temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

404. Sum of Left Leaves

DFS:

public int sumOfLeftLeaves(TreeNode root) {
    if(root==null){
        return 0;
    }
    int res=0;
    if(root.left!=null &&
            root.left.left==null && root.left.right==null){
        res+=root.left.val;
        return res+sumOfLeftLeaves(root.right);
    }else{
        return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
    }
}

BFS:

public int sumOfLeftLeaves(TreeNode root) {
    Set<TreeNode> set=new HashSet<>();
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    int res=0;
    while(!q.isEmpty()){
        TreeNode node=q.poll();
        if(set.contains(node)
                && node.left==null && node.right==null){
            res+=node.val;
        }else{
            if(node.left!=null){
                q.offer(node.left);
                set.add(node.left);
            }
            if(node.right!=null){
                q.offer(node.right);
            }
        }
    }
    return res;
}

407. Trapping Rain Water II

public class Cell {
    int row;
    int col;
    int height;
    public Cell(int row, int col, int height) {
        this.row = row;
        this.col = col;
        this.height = height;
    }
}

public int trapRainWater(int[][] heights) {
    if (heights == null || heights.length == 0 || heights[0].length == 0)
        return 0;

    PriorityQueue<Cell> queue = new PriorityQueue<>(1, new Comparator<Cell>(){
        public int compare(Cell a, Cell b) {
            return a.height - b.height;
        }
    });
    
    int m = heights.length;
    int n = heights[0].length;
    boolean[][] visited = new boolean[m][n];

    // Initially, add all the Cells which are on borders to the queue.
    for (int i = 0; i < m; i++) {
        visited[i][0] = true;
        visited[i][n - 1] = true;
        queue.offer(new Cell(i, 0, heights[i][0]));
        queue.offer(new Cell(i, n - 1, heights[i][n - 1]));
    }

    for (int i = 0; i < n; i++) {
        visited[0][i] = true;
        visited[m - 1][i] = true;
        queue.offer(new Cell(0, i, heights[0][i]));
        queue.offer(new Cell(m - 1, i, heights[m - 1][i]));
    }

    // from the borders, pick the shortest cell visited and check its neighbors:
    // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped
   // add all its neighbors to the queue.
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int res = 0;
    while (!queue.isEmpty()) {
        Cell cell = queue.poll();
        for (int[] dir : dirs) {
            int row = cell.row + dir[0];
            int col = cell.col + dir[1];
            if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {
                visited[row][col] = true;
                res += Math.max(0, cell.height - heights[row][col]);
                queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));
            }
        }
    }
    
    return res;
}

433. Minimum Genetic Mutation

public int minMutation(String startGene, String endGene, String[] bank) {
    Deque<String> q=new LinkedList<>();
    q.offer(startGene);
    int level=0;
    Set<String> visited=new HashSet<>();
    visited.add(startGene);
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            String cur=q.poll();
            if(cur.equals(endGene)){
                return level;
            }
            for (String s : bank) {
                if(!visited.contains(s) && isNext(cur,s)){
                    visited.add(s);
                    q.offer(s);
                }
            }
        }
        level++;
    }
    return -1;
}

boolean isNext(String a, String b){
    int count=0;
    int n=a.length();
    for (int i = 0; i < n; i++) {
        if(a.charAt(i)!=b.charAt(i)){
            count++;
            if(count>1){
                return false;
            }
        }
    }
    return count==1;
}

542. 01 Matrix

public int[][] updateMatrix(int[][] mat) {
    int row=mat.length;
    int col=mat[0].length;
    int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
    Deque<int[]> q=new LinkedList<>();
    int[][] dist=new int[row][col];
    for (int[] ints : dist) {
        Arrays.fill(ints,Integer.MAX_VALUE);
    }
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(mat[i][j]==0){
                dist[i][j]=0;
                q.offer(new int[]{i,j});
            }
        }
    }
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        int d=dist[i][j];
        for (int[] dir : dirs) {
            int x=i+dir[0];
            int y=j+dir[1];
            if(x>=0 && x<row && y>=0 && y<col){
                if(d+1<dist[x][y]){
                    dist[x][y]=d+1;
                    q.offer(new int[]{x,y});
                }
            }
        }
    }
    return dist;
}

623. Add One Row to Tree

if(depth==1){
    return new TreeNode(val,root,null);
}
Deque<TreeNode> q=new LinkedList<>();
q.offer(root);
int i=1;
while(!q.isEmpty()){
    int size=q.size();
    if(i==depth-1){
        while(size-->0){
            TreeNode node=q.poll();
            TreeNode newLeft=new TreeNode(val);
            TreeNode newRight=new TreeNode(val);
            newLeft.left=node.left;
            newRight.right=node.right;
            node.left=newLeft;
            node.right=newRight;
        }
        return root;
    }
    while(size-->0){
        TreeNode node=q.poll();
        if(node.left!=null){
            q.offer(node.left);
        }
        if(node.right!=null){
            q.offer(node.right);
        }
    }
    i++;
}
return null;

662. Maximum Width of Binary Tree

public int widthOfBinaryTree(TreeNode root) {
    Deque<Pair<TreeNode,Integer>> q=new LinkedList<>();
    q.offer(new Pair<>(root,1));
    int res=1;
    while(!q.isEmpty()){
        int size=q.size();
        int count=0;
        int l=1;
        int r=1;
        while(count<size){
            Pair<TreeNode,Integer> cur=q.poll();
            TreeNode node=cur.getKey();
            int index=cur.getValue();
            if(count==0){
                l=index;
            }
            if(count==size-1){
                r=index;
            }
            if(node.left!=null){
                q.offer(new Pair<>(node.left,2*index));
            }
            if(node.right!=null){
                q.offer(new Pair<>(node.right,2*index+1));
            }
            count++;
        }
        res=Math.max(res,r-l+1);
    }
    return res;
}

785. Is Graph Bipartite?