Cut Off Trees for Golf Event

Hard
1685.

Cut Off Trees for Golf Event

Cut Off Trees for Golf Event is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon and Google interviews.

A forest is given as an m x n matrix forest:

  • 0 is an obstacle that cannot be walked through,
  • 1 is open ground,
  • a number greater than 1 is 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.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 10^9
  • forest[0][0] != 0
  • all heights greater than 1 are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} forest
 * @return {number}
 */
var cutOffTree = function(forest) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

A forest is given as an m x n matrix forest:

  • 0 is an obstacle that cannot be walked through,
  • 1 is open ground,
  • a number greater than 1 is 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.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 10^9
  • forest[0][0] != 0
  • all heights greater than 1 are distinct

Hints for Cut Off Trees for Golf Event

  1. 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).

  2. 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).

  3. 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

  1. Collect every cell with value > 1 as (height, row, col) and sort by height.
  2. Set the current position to (0, 0) and the total to 0.
  3. 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.
  4. 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 total

Java

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