Cut Off Trees for Golf Event — Problem & Solution
Cut Off Trees for Golf Event solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Cut Off Trees for Golf Event is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Matrix, Breadth-First Search, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A forest is given as an m x n matrix forest:
0is an obstacle that cannot be walked through,1is open ground,- a number greater than
1is a tree of that height; it can be walked through too.
You start at cell (0, 0) and each step moves one cell up, down, left or right. You must cut down every tree, in order from the shortest to the tallest. Cutting a tree turns its cell into open ground (1). All tree heights are distinct.
Return the minimum number of steps needed to cut all the trees, or -1 if some tree cannot be reached.
Example 1
Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: The trees 2, 3, 4, 5, 6, 7 lie along one path from the start, one step apart.
Example 2
Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The middle row is a wall: trees 5, 6 and 7 are out of reach.
Example 3
Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
Explanation: Tree 2 stands on the start cell, so it is cut without moving.
Constraints
m == forest.lengthn == forest[i].length1 <= m, n <= 500 <= forest[i][j] <= 10^9forest[0][0] != 0all heights greater than 1 are distinct
Hints for Cut Off Trees for Golf Event
Hint 1
The order of the cuts is fixed: sort the trees by height. The total is the sum of the walking distances between consecutive targets, starting from
(0, 0).Hint 2
Walking from one target to the next is an independent shortest-path question on a grid whose obstacles never change (a cut tree still lets you pass).
Hint 3
Run a BFS for each leg. If any leg's target is unreachable, the answer is
-1.
How to solve Cut Off Trees for Golf Event
Since the trees must be cut in height order and cutting never changes which cells are walkable, the problem splits into independent legs: from the start to the shortest tree, from there to the next, and so on. Each leg is a breadth-first search.
Approach
- Collect every cell with value
> 1as(height, row, col)and sort by height. - Set the current position to
(0, 0)and the total to0. - For each tree in order, BFS from the current position to the tree over cells that are not
0. If it is unreachable, return-1; otherwise add the distance and move to the tree. - Return the total.
Why it works
Every cell except an obstacle is walkable before and after its tree is cut, so the grid's walkable set is fixed. The cost of a leg therefore depends only on its two endpoints, and the minimum total is the sum of the minimum legs. BFS gives the exact shortest leg on an unweighted grid.
Complexity
- Time —
O(T · m · n) for T trees — at most O((m · n)^2) - Space —
O(m · n)
Pitfalls
- A tree on
(0, 0)costs zero steps — the first leg can have length 0. - Trees are not obstacles: you may walk across taller trees on the way to a shorter one.
- Reset the visited marks for every BFS.
Reference solution
Python
from collections import deque
from typing import List
def cutOffTree(forest: List[List[int]]) -> int:
m, n = len(forest), len(forest[0])
trees = sorted((forest[r][c], r, c) for r in range(m) for c in range(n) if forest[r][c] > 1)
def bfs(sr, sc, tr, tc):
if sr == tr and sc == tc:
return 0
seen = [[False] * n for _ in range(m)]
seen[sr][sc] = True
q = deque([(sr, sc, 0)])
while q:
r, c, d = q.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and forest[nr][nc] != 0:
if nr == tr and nc == tc:
return d + 1
seen[nr][nc] = True
q.append((nr, nc, d + 1))
return -1
total, r, c = 0, 0, 0
for _, tr, tc in trees:
d = bfs(r, c, tr, tc)
if d < 0:
return -1
total += d
r, c = tr, tc
return totalJava
public static int cutOffTree(int[][] forest) {
int m = forest.length, n = forest[0].length;
List<int[]> trees = new ArrayList<>();
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (forest[r][c] > 1) trees.add(new int[]{forest[r][c], r * n + c});
trees.sort((x, y) -> Integer.compare(x[0], y[0]));
int total = 0, pos = 0;
for (int[] t : trees) {
int d = cotBfs(forest, m, n, pos, t[1]);
if (d < 0) return -1;
total += d;
pos = t[1];
}
return total;
}
static int cotBfs(int[][] forest, int m, int n, int s, int t) {
if (s == t) return 0;
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int[] dist = new int[m * n];
Arrays.fill(dist, -1);
int[] q = new int[m * n];
int head = 0, tail = 0;
dist[s] = 0;
q[tail++] = s;
while (head < tail) {
int cur = q[head++], r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || forest[nr][nc] == 0) continue;
int x = nr * n + nc;
if (dist[x] != -1) continue;
dist[x] = dist[cur] + 1;
if (x == t) return dist[x];
q[tail++] = x;
}
}
return -1;
}C++
static int cotBfs(vector<vector<int>>& forest, int m, int n, int s, int t) {
if (s == t) return 0;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<int> dist(m * n, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop();
int r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || forest[nr][nc] == 0) continue;
int x = nr * n + nc;
if (dist[x] != -1) continue;
dist[x] = dist[cur] + 1;
if (x == t) return dist[x];
q.push(x);
}
}
return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
int m = forest.size(), n = forest[0].size();
vector<pair<int, int>> trees;
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (forest[r][c] > 1) trees.push_back({forest[r][c], r * n + c});
sort(trees.begin(), trees.end());
int total = 0, pos = 0;
for (auto& t : trees) {
int d = cotBfs(forest, m, n, pos, t.second);
if (d < 0) return -1;
total += d;
pos = t.second;
}
return total;
}JavaScript
var cutOffTree = function(forest) {
var m = forest.length, n = forest[0].length;
var trees = [];
for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) if (forest[r][c] > 1) trees.push([forest[r][c], r, c]);
trees.sort(function(x, y) { return x[0] - y[0]; });
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var bfs = function(s, t) {
if (s === t) return 0;
var dist = new Array(m * n);
for (var i = 0; i < m * n; i++) dist[i] = -1;
dist[s] = 0;
var q = [s];
for (var h = 0; h < q.length; h++) {
var cr = Math.floor(q[h] / n), cc = q[h] % n;
for (var k = 0; k < 4; k++) {
var nr = cr + dr[k], nc = cc + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || forest[nr][nc] === 0) continue;
var x = nr * n + nc;
if (dist[x] !== -1) continue;
dist[x] = dist[q[h]] + 1;
if (x === t) return dist[x];
q.push(x);
}
}
return -1;
};
var total = 0, pos = 0;
for (var j = 0; j < trees.length; j++) {
var target = trees[j][1] * n + trees[j][2];
var d = bfs(pos, target);
if (d < 0) return -1;
total += d;
pos = target;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal