# Java solution, PriorityQueue + BFS

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) {
}
}
}

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];
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;
visited[nr][nc] = true;
}
}
step++;
}

return -1;
}
}
``````

• This post is deleted!

• Exactly the same idea!

• What will be the runtime for this solution?

• @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...

• @SanD Added run time analysis.

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

Thanks for the solution!

• @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.

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

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

You are guaranteed that no two trees have the same height

• 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}};
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)){
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);
}
}
}``````

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

• This post is deleted!

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