Java solution explained
Before moving into the solution there are a couple of questions to be asked during the interview.\n What if the first cell is 0?\n Can there be a tree in the st
Before moving into the solution there are a couple of questions to be asked during the interview.\n* What if the first cell is 0?\n* Can there be a tree in the start location (0, 0)?\n* Can we walk though the trees?\n* What is the behaviour if there are trees with same height? Is there any preference order to be considered?\n\nKeeping the above points in mind, we can arrive at the below algorithm.\n* Define a class which stores the cell information containing x, y location and the tree height.\n* We need trees sorted in non-decreasing order while travelling through the forest. A min heap (priority queue) is a good choice for the same.\n* While adding cell information to the min heap, make sure only the trees are added and not the cells containing 0 or 1.\n* We need to find out the minimum distance to be travelled from the given source and the destination. We can pick BFS to find it.\n\nWhen do I know if there is no possible path to cut all the trees in the forest?\n* If the start location contains a 0 value.\n* If there is no path for the given source and destination, i.e no path between tree1 and tree2 with increasing heights.\n\n```\nclass Solution {\n    class Cell implements Comparable<Cell> {\n        int x;\n        int y;\n        int tree;\n        public Cell(int x, int y, int tree) {\n            this.x = x;\n            this.y = y;\n            this.tree = tree;\n        }\n        public int compareTo(Cell cell) {\n            return this.tree <= cell.tree ? -1 : 1;\n        }\n        public boolean equals(Cell cell) {\n            return this.x == cell.x && this.y == cell.y;\n        }\n    }\n    \n    int N, M;\n    public int cutOffTree(List<List<Integer>> forest) {\n        PriorityQueue<Cell> pq = new PriorityQueue<>();\n        N = forest.size();\n        M = forest.get(0).size();\n        for(int i=0; i<N; i++) {\n            for(int j=0; j<M; j++) {\n                if(forest.get(i).get(j) > 1)\n                    pq.add(new Cell(i, j, forest.get(i).get(j)));\n            }\n        }\n        \n        int minPath = 0;\n        if(forest.get(0).get(0) == 0) {\n            return -1;\n        }\n        \n        Cell source = new Cell(0,0,forest.get(0).get(0));\n        while(!pq.isEmpty()) {\n            Cell dest = pq.remove();\n            int path = getMinPath(forest, source, dest);\n            if(path == -1)\n                return -1;\n\n            minPath += path;\n            source = dest;\n        }\n        \n        return minPath;\n    }\n    \n    int[][] dir = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};\n    private int getMinPath(List<List<Integer>> forest, Cell source, Cell dest) {\n        Deque<Cell> queue = new ArrayDeque<>();\n        boolean[][] isVisited = new boolean[N][M];\n        queue.add(source);\n        int path = 0;\n        while(!queue.isEmpty()) {\n            int size = queue.size();\n            while(size-- > 0) {\n                Cell cell = queue.remove();\n                if(cell.equals(dest)) {\n                    return path;\n                }\n                \n                for(int k=0; k<4; k++) {\n                    int x = cell.x + dir[k][0];\n                    int y = cell.y + dir[k][1];\n                    if(checkBoundary(x, y, N, M) && !isVisited[x][y] && forest.get(x).get(y) != 0) {\n                        queue.add(new Cell(x, y, forest.get(x).get(y)));\n                        isVisited[x][y] = true;\n                    }\n                }\n            }\n            path++;\n        }\n        \n        return -1;\n    }\n    \n    private boolean checkBoundary(int x, int y, int N, int M) {\n        return x>=0 && y>=0 && x<N && y<M;\n    }\n}\n```\n
[]