Java solution, PriorityQueue + BFS


  • 27
    1. Since we have to cut trees in order of their height, we first put trees (int[] {row, col, height}) into a priority queue and sort by height.
    2. Poll each tree from the queue and use BFS to find out steps needed.

    The worst case time complexity could be O(m^2 * n^2) (m = number of rows, n = number of columns) since there are m * n trees and for each BFS worst case time complexity is O(m * n) too.

    class Solution {
        static int[][] dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};
    
        public int cutOffTree(List<List<Integer>> forest) {
            if (forest == null || forest.size() == 0) return 0;
            int m = forest.size(), n = forest.get(0).size();
    
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (forest.get(i).get(j) > 1) {
                        pq.add(new int[] {i, j, forest.get(i).get(j)});
                    }
                }
            }
    
            int[] start = new int[2];
            int sum = 0;
            while (!pq.isEmpty()) {
                int[] tree = pq.poll();
                int step = minStep(forest, start, tree, m, n);
    
                if (step < 0) return -1;
                sum += step;
    
                start[0] = tree[0];
                start[1] = tree[1];
            }
    
            return sum;
        }
    
        private int minStep(List<List<Integer>> forest, int[] start, int[] tree, int m, int n) {
            int step = 0;
            boolean[][] visited = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.add(start);
            visited[start[0]][start[1]] = true;
    
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] curr = queue.poll();
                    if (curr[0] == tree[0] && curr[1] == tree[1]) return step;
    
                    for (int[] d : dir) {
                        int nr = curr[0] + d[0];
                        int nc = curr[1] + d[1];
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n 
                            || forest.get(nr).get(nc) == 0 || visited[nr][nc]) continue;
                        queue.add(new int[] {nr, nc});
                        visited[nr][nc] = true;
                    }
                }
                step++;
            }
    
            return -1;
        }
    }
    

  • 0
    This post is deleted!

  • 0

    Exactly the same idea!


  • 2
    S

    What will be the runtime for this solution?


  • 0

    @diddit said in Java solution, PriorityQueue + BFS:

    can be start = tree;

    Not really... start is int[2] but tree is int[3] though doing this won't break the code...


  • 1

    @SanD Added run time analysis.


  • 0
    J

    @shawngao in Java
    int[] start = new int[2];
    Initialzes the list with 0 right?

    Thanks for the solution!


  • 0
    M

    @jerom.chai-gmail.com
    In JAVA, an int array is initialized by 0.
    This is language feature and implemented by JAVA runtime. No need to implement in code.


  • 0
    F

    Does the solution consider the case multiple trees with same height ?


  • 0
    M

    @foggerwoody
    I don't think so because the description says:

    You are guaranteed that no two trees have the same height


  • 0

    Same idea, use class instead of int array.

    class Solution {
        public int cutOffTree(List<List<Integer>> forest) {
           int m = forest.size();
           if(m == 0) return 0;
           int n = forest.get(0).size();
           PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) ->{
             return a.h - b.h;
           });
            
           for(int i = 0; i < m; i++){
             for(int j = 0; j < n; j++){
                int h = forest.get(i).get(j); 
                if(h > 1){
                   pq.offer(new Node(i, j, h)); 
                } 
             }  
           }
            
           Node source = new Node(0, 0, 0);
           Node target = null;
           int res = 0; 
           while(!pq.isEmpty()){
             target = pq.poll();  
             int distance = helper(forest, source, target);  
             if(distance == -1) return -1;
             else res  +=   distance;
             source = target;  
           }  
           return res; 
        }
        
        int helper(List<List<Integer>> forest, Node source, Node target){
            int m = forest.size(), n = forest.get(0).size(); 
            int[][] dir = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
            Queue<Node> q = new LinkedList<Node>();
            Set<Node> visited = new HashSet<Node>();
            q.offer(source);
            int step = 0;
            while(!q.isEmpty()){
              int size = q.size();
              for(int i = 0; i < size; i++){
                  Node node =  q.poll();
                  if(node.equals(target)){
                    return step;  
                  }
                  for(int[] row: dir){
                     int x = node.x + row[0];
                     int y = node.y + row[1];
                     if(x < 0 || y < 0 || x >= m || y >= n || forest.get(x).get(y) == 0 ){
                        continue; 
                     } 
                     Node newNode = new Node(x, y, forest.get(x).get(y));
                     if(!visited.contains(newNode)){
                        visited.add(newNode); 
                        q.offer(newNode); 
                     } 
                  }                
              }
              step++;  
            }
            return -1;
        }
        
        class Node{
           int x, y;
           int h;
           Node(int xx, int yy, int hh){
             x = xx;
             y = yy;
             h = hh;  
           } 
           
           	public int hashCode(){
                return x * 31 + y;
            } 
            
            public boolean equals(Object obj){
                Node other = (Node)obj;
                return (other.x == x) && (other.y == y);
            }
        }
    }

  • 0

    Does your solution get accepted? I wrote the code with the same idea but got TLE


  • 0
    S
    This post is deleted!

Log in to reply
 

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