Showing posts with label Breadth-first Search. Show all posts
Showing posts with label Breadth-first Search. Show all posts

Saturday, January 24, 2015

Number of Countries

Question: 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4

Idea: Breadth-first search. For each untagged block, start breadth-first-search and marked the visited block with a specific TAG. When all the board has been marked, return the result.

Time: O(n^2) Space: O(n)

Code: 
 public class CountryNumber {  
      public CountryNumber()  
      {  
           int[][] input1={{1,1,1,0},{1,1,0,0},{0,0,0,1}};  
           int[][] input2={{1,1,1,1},{0,0,0,0},{1,0,0,1}};  
           printMatrix(input2);  
           System.out.println(solution(input2));  
      }  
      public void printMatrix(int[][] matrix)  
      {  
           for(int i=0;i<matrix.length;i++)  
           {  
                for(int j=0;j<matrix[0].length;j++)  
                {  
                     System.out.print(matrix[i][j]);  
                     System.out.print(' ');  
                }  
                System.out.print("\n");  
           }  
      }  
      public class Block{  
           int x;  
           int y;  
           public Block(int x,int y)  
           {  
                this.x=x;  
                this.y=y;  
           }  
      }  
      public int solution(int[][] board)  
      {  
           int TAG=Integer.MIN_VALUE;  
           int counter=0;  
           for(int i=0;i<board.length;i++)  
           {  
                for(int j=0;j<board[0].length;j++)  
                {  
                     if(board[i][j]!=TAG)  
                     {  
                          bfs(board,i,j);  
                          counter+=1;  
                     }  
                }  
           }  
           return counter;  
      }  
      public void bfs(int[][] board,int startX,int startY)  
      {  
           int TAG1=Integer.MIN_VALUE;  
           int TAG2=board[startX][startY];  
           int m=board.length;  
           int n=board[0].length;  
           Queue<Block> queue=new LinkedList<Block>();  
           queue.offer(new Block(startX,startY));  
           while(queue.isEmpty()==false)  
           {  
                int queueSize=queue.size();  
                for(int i=0;i<queue.size();i++)  
                {  
                     Block cur=queue.poll();  
                     board[cur.x][cur.y]=TAG1;  
                     if(cur.x+1<m&&board[cur.x+1][cur.y]==TAG2)  
                          queue.offer(new Block(cur.x+1,cur.y));  
                     if(cur.y+1<n&&board[cur.x][cur.y+1]==TAG2)  
                          queue.offer(new Block(cur.x,cur.y+1));  
                     if(cur.x-1>=0&&board[cur.x-1][cur.y]==TAG2)  
                          queue.offer(new Block(cur.x-1,cur.y));  
                     if(cur.y-1>=0&&board[cur.x][cur.y-1]==TAG2)  
                          queue.offer(new Block(cur.x,cur.y-1));  
                }  
           }  
      }  
 }  

Wednesday, January 21, 2015

Surrounded Regions (LeetCode Breadth-first Search)

Question: Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

Idea: For each 'O' at boundary, do breadth-first search to mark the reachable block as '#'. Then scan the matrix and mark all non-'#' blocks as 'X' and '#' blocks as 'O'.

Time: O(n^2) Space: O(n^2)

Code:
 public class Solution {  
   public class Block{  
     int x;  
     int y;  
     public Block(int x,int y)  
     {  
       this.x=x;  
       this.y=y;  
     }  
   }  
   public void solve(char[][] board) {  
     if(board.length==0||board[0].length==0)  
       return;  
     int m=board.length;  
     int n=board[0].length;  
     for(int j=0;j<n;j++)  
     {  
       if(board[0][j]=='O')  
         bfs(board,0,j);  
       if(board[m-1][j]=='O')  
         bfs(board,m-1,j);  
     }  
     for(int i=0;i<m;i++)  
     {  
       if(board[i][0]=='O')  
         bfs(board,i,0);  
       if(board[i][n-1]=='O')  
         bfs(board,i,n-1);  
     }  
     for(int i=0;i<m;i++)  
     {  
       for(int j=0;j<n;j++)  
       {  
         if(board[i][j]=='#')  
           board[i][j]='O';  
         else  
           board[i][j]='X';  
       }  
     }  
   }  
   public void bfs(char[][] board,int startX,int startY)  
   {  
     int m=board.length;  
     int n=board[0].length;  
     Queue<Block> queue=new LinkedList<Block>();  
     queue.offer(new Block(startX,startY));  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       for(int i=0;i<queueSize;i++)  
       {  
         Block cur=queue.poll();  
         if(board[cur.x][cur.y]=='O')  
         {  
           board[cur.x][cur.y]='#';  
           if(cur.x+1<m&&board[cur.x+1][cur.y]=='O')  
             queue.offer(new Block(cur.x+1,cur.y));  
           if(cur.x-1>=0&&board[cur.x-1][cur.y]=='O')  
             queue.offer(new Block(cur.x-1,cur.y));  
           if(cur.y+1<n&&board[cur.x][cur.y+1]=='O')  
             queue.offer(new Block(cur.x,cur.y+1));  
           if(cur.y-1>=0&&board[cur.x][cur.y-1]=='O')  
             queue.offer(new Block(cur.x,cur.y-1));  
         }  
       }  
     }  
   }  
 }  

Word Ladder II (LeetCode Backtracking)

Question: Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Idea: Dijkstra's algorithm. Image the words as nodes and the ladder as edges, this is exactly a shortest path problem from the node start (source) to the node end (destination). Without the Boost library in C++, we need to a little bit patience to implement the Dijkstra's algorithm in Java.

First add the start and the end to the dictionary. Then use breadth-first search to flood from the start node to all the reachable nodes (even further than end nodes), and label the distance between the current node and the start node. At the same time, for each node, create single direction edges to its source.

After the flood, start from the end node to construct path to the start node, since the edges we constructed are single directional and are from destination to source. Assume the distance between the node and the start node is x, then the next hop y of this node should follow two conditions:
1) y is x's neighbor (has constructed edge)
2) distance[y=>start]==distance[x=>start]-1
So following these two rules, use depth-first search to construct the path until the start node is reached. Do not forget to reverse the paths constructed before output, since the requirement is source to destination.


Time: O(n^2) (The fastest implementation of Dijkstra's algorithm is O(e+vlgv))
Space: O(n^2)

Code:
 public class Solution {  
   public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
     List<List<String>> result=new ArrayList<List<String>>();  
     if(dict==null||dict.size()==0)  
       return result;  
     HashMap<String,List<String>> graph=new HashMap<String,List<String>>();  
     HashMap<String, Integer> distance=new HashMap<String,Integer>();  
     dict.add(start);  
     dict.add(end);  
     bfs(graph,distance,start,end,dict);  
     List<String> path=new ArrayList<String>();  
     dfs(result,path,graph,distance,start,end);  
     return result;  
   }  
   public void dfs(List<List<String>> result,List<String> path, HashMap<String,List<String>> graph,HashMap<String,Integer> distance,String start,String cur)  
   {  
     path.add(cur);  
     if(path.contains(start))  
     {  
       Collections.reverse(path);  
       result.add(new ArrayList<String>(path));  
       Collections.reverse(path);  
     }  
     else  
     {  
       for(String next:graph.get(cur))  
       {  
         if(distance.containsKey(next)&&distance.get(cur)==distance.get(next)+1)  
         {  
           dfs(result,path,graph,distance,start,next);  
         }  
       }  
     }  
     path.remove(path.size()-1);  
   }  
   public void bfs(HashMap<String,List<String>> graph, HashMap<String,Integer> distance,String start, String end, Set<String> dict)  
   {  
     Queue<String> queue=new LinkedList<String>();  
     queue.offer(start);  
     distance.put(start,0);  
     for(String s:dict)  
     {  
       graph.put(s,new ArrayList<String>());  
     }  
     while(queue.isEmpty()==false)  
     {  
       String cur=queue.poll();  
       List<String> neighbors=getNeighbors(cur,dict);  
       for(String neighbor:neighbors)  
       {  
         graph.get(neighbor).add(cur);  
         if(distance.containsKey(neighbor)==false)  
         {  
           distance.put(neighbor,distance.get(cur)+1);  
           queue.offer(neighbor);  
         }  
       }  
     }  
   }  
   public List<String> getNeighbors(String cur, Set<String> dict)  
   {  
     List<String> result=new ArrayList<String>();  
     for(int i=0;i<cur.length();i++)  
     {  
       for(char c='a';c<='z';c++)  
       {  
         if(c!=cur.charAt(i))  
         {  
           String maybe=replaceCharAt(cur,i,c);  
           if(dict.contains(maybe))  
             result.add(maybe);  
         }  
       }  
     }  
     return result;  
   }  
   public String replaceCharAt(String s, int index, char c)  
   {  
     char[] chars=s.toCharArray();  
     chars[index]=c;  
     return new String(chars);  
   }  
 }  

Thursday, January 15, 2015

Populating Next Right Pointers in Each Node II (LeetCode Tree)

Question: Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Idea: Both depth-first search and breadth-first search work with the same time complexity. However, depth-first search is more space efficient. For depth-first search, always keeps track of the previous node to jump through the missing leaves. For breadth-first search, use a queue to remember each row.

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public void connect(TreeLinkNode root) {  
     if(root==null)  
       return;  
     TreeLinkNode parent=root;  
     TreeLinkNode pre;  
     TreeLinkNode next;  
     while(parent!=null)  
     {  
       pre=null;  
       next=null;  
       while(parent!=null)  
       {  
         if(next==null)  
           next=(parent.left!=null)?parent.left:parent.right;  
         if(parent.left!=null)  
         {  
           if(pre!=null)  
           {  
             pre.next=parent.left;  
             pre=pre.next;  
           }  
           else  
             pre=parent.left;  
         }  
         if(parent.right!=null)  
         {  
           if(pre!=null)  
           {  
             pre.next=parent.right;  
             pre=pre.next;  
           }  
           else  
             pre=parent.right;  
         }  
         parent=parent.next;  
       }  
       parent=next;  
     }  
   }  
 }  

Populating Next Right Pointers in Each Node (LeetCode Tree)

Question: Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Idea: Breadth-first search. If the node visited is not the last node in the level, connect it to the next node in the queue. Depth-first search method is the same, just remember the last node.

Time: O(n) Space: O(n) for breadth-first search, O(1) for depth-first search.

Breadth-first Search Code:
 public class Solution {  
   public void connect(TreeLinkNode root) {  
     if(root==null)   
       return;  
     Queue<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();  
     queue.offer(root);  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       for(int i=0;i<queueSize;i++)  
       {  
         TreeLinkNode cur=queue.poll();  
         if(i!=queueSize-1)  
         {  
           cur.next=queue.peek();  
         }  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
     }  
   }  
 }  

Depth-first Search Code:
 public class Solution {  
   public void connect(TreeLinkNode root) {  
     if(root==null)  
       return;  
     TreeLinkNode parent=root;  
     TreeLinkNode next=parent.left;  
     while(parent!=null&&next!=null)  
     {  
       TreeLinkNode prev=null;  
       while(parent!=null)  
       {  
         if(prev==null)  
           prev=parent.left;  
         else  
         {  
           prev.next=parent.left;  
           prev=prev.next;  
         }  
         prev.next=parent.right;  
         prev=prev.next;  
         parent=parent.next;  
       }  
       parent=next;  
       next=parent.left;  
     }  
   }  
 }  

Binary Tree Zigzag Level Order Traversal (LeetCode Tree)

Question: Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Idea: Breadth-first search. Maintain a flag to reverse the direction of the next row.

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(root==null)  
       return result;  
     Queue<TreeNode> queue=new LinkedList<TreeNode>();  
     queue.offer(root);  
     boolean reverse=false;  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       List<Integer> row=new ArrayList<Integer>();  
       for(int i=0;i<queueSize;i++)  
       {  
         TreeNode cur=queue.poll();  
         if(reverse==true)  
         {  
           row.add(0,cur.val);  
         }  
         else  
         {  
           row.add(cur.val);  
         }  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
       result.add(row);  
       reverse=!reverse;  
     }  
     return result;  
   }  
 }  

Wednesday, January 14, 2015

Binary Tree Level Order Traversal II (LeetCode Tree)

Question: Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

Idea: Breadth-first search. Use a queue to maintain the nodes in the next level. Whenever a level is visited, insert it at the front of the result, then the result will be bottom-up order.

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public List<List<Integer>> levelOrderBottom(TreeNode root) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(root==null)  
       return result;  
     Queue<TreeNode> queue=new LinkedList<TreeNode>();  
     queue.offer(root);  
     while(queue.isEmpty()==false)  
     {  
       int number=queue.size();  
       ArrayList<Integer> aLevel=new ArrayList<Integer>();  
       for(int i=0;i<number;i++)  
       {  
         TreeNode cur=queue.poll();  
         aLevel.add(cur.val);  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
       result.add(0,aLevel);  
     }  
     return result;  
   }  
 }  

Binary Tree Level Order Traversal (LeetCode Tree)

Question: 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,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Idea: Breadth-first search. Use a queue to maintain the next level.

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public List<List<Integer>> levelOrder(TreeNode root) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(root==null)  
       return result;  
     Queue<TreeNode> queue=new LinkedList<TreeNode>();  
     queue.offer(root);  
     while(!queue.isEmpty())  
     {  
       int number=queue.size();  
       List<Integer> tmp=new ArrayList<Integer>();  
       for(int i=0;i<number;i++)  
       {  
         TreeNode cur=queue.poll();  
         tmp.add(cur.val);  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
       result.add(tmp);  
     }  
     return result;  
   }  
 }  

Monday, January 12, 2015

Word Ladder (LeetCode String)

Question: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Idea: Breadth-first search. Initial the queue with the input start, then do level by level search until reaching the target or can not go further. To enqueue the next level, we need to use a trick to reduce the time for exhaustivity.

Time: O(nw^26) Space: O(n) (where n is the size of the dict, w is the width of each word in the dict).

Code:
 public class Solution {  
   public int ladderLength(String start, String end, Set<String> dict) {  
     Queue<String> queue=new LinkedList<String>();  
     queue.offer(start);  
     dict.remove(start);  
     int numRuns=1;  
     boolean found=false;  
     while(queue.isEmpty()==false)  
     {  
       int queueLength=queue.size();  
       for(int i=0;i<queueLength;i++)  
       {  
         String cur=queue.poll();  
         if(cur.equals(end))  
           return numRuns;  
         for(int j=0;j<cur.length();j++)  
         {  
           for(char c='a';c<='z';c++)  
           {  
             if(c!=cur.charAt(j))  
             {  
               String tmp=replaceAt(cur,j,c);  
               if(dict.contains(tmp))  
               {  
                 queue.offer(tmp);  
                 dict.remove(tmp);  
               }  
             }  
           }  
         }  
       }  
       numRuns++;  
     }  
     return 0;  
   }  
   public String replaceAt(String s,int index, char c)  
   {  
     char[] chars=s.toCharArray();  
     chars[index]=c;  
     return new String(chars);  
   }  
 }