Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

675. Cut Off Trees for Golf Event - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def cutOffTree(self, forest):
        if not forest or not forest[0]:
            return -1

        rows, cols = len(forest), len(forest[0])

        # Collect all trees in sorted order of height
        trees = sorted((h, r, c)
                       for r, row in enumerate(forest)
                       for c, h in enumerate(row) if h > 1)

        def bfs(sr, sc, tr, tc):
            if sr == tr and sc == tc:
                return 0
            visited = [[False] * cols for _ in range(rows)]
            queue = deque([(sr, sc, 0)])
            visited[sr][sc] = True
            while queue:
                r, c, d = queue.popleft()
                for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and forest[nr][nc] != 0:
                        if nr == tr and nc == tc:
                            return d + 1
                        visited[nr][nc] = True
                        queue.append((nr, nc, d + 1))
            return -1

        total_steps = 0
        sr = sc = 0
        for _, tr, tc in trees:
            steps = bfs(sr, sc, tr, tc)
            if steps == -1:
                return -1
            total_steps += steps
            sr, sc = tr, tc
        return total_steps
      
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        int rows = forest.size(), cols = forest[0].size();
        vector<tuple<int,int,int>> trees;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (forest[r][c] > 1)
                    trees.push_back({forest[r][c], r, c});
        sort(trees.begin(), trees.end());

        auto bfs = [&](int sr, int sc, int tr, int tc) {
            if (sr == tr && sc == tc) return 0;
            vector<vector<bool>> visited(rows, vector<bool>(cols, false));
            queue<tuple<int,int,int>> q;
            q.push({sr, sc, 0});
            visited[sr][sc] = true;
            int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
            while (!q.empty()) {
                auto [r, c, d] = q.front(); q.pop();
                for (auto& dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && forest[nr][nc] != 0) {
                        if (nr == tr && nc == tc) return d + 1;
                        visited[nr][nc] = true;
                        q.push({nr, nc, d + 1});
                    }
                }
            }
            return -1;
        };

        int sr = 0, sc = 0, total_steps = 0;
        for (auto& [_, tr, tc] : trees) {
            int steps = bfs(sr, sc, tr, tc);
            if (steps == -1) return -1;
            total_steps += steps;
            sr = tr; sc = tc;
        }
        return total_steps;
    }
};
      
import java.util.*;

class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        int rows = forest.size(), cols = forest.get(0).size();
        List<int[]> trees = new ArrayList<>();
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (forest.get(r).get(c) > 1)
                    trees.add(new int[]{forest.get(r).get(c), r, c});
        trees.sort(Comparator.comparingInt(a -> a[0]));

        int sr = 0, sc = 0, total_steps = 0;
        for (int[] tree : trees) {
            int steps = bfs(forest, sr, sc, tree[1], tree[2]);
            if (steps == -1) return -1;
            total_steps += steps;
            sr = tree[1]; sc = tree[2];
        }
        return total_steps;
    }

    private int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
        if (sr == tr && sc == tc) return 0;
        int rows = forest.size(), cols = forest.get(0).size();
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc, 0});
        visited[sr][sc] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] dir : dirs) {
                int nr = curr[0] + dir[0], nc = curr[1] + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                    !visited[nr][nc] && forest.get(nr).get(nc) != 0) {
                    if (nr == tr && nc == tc) return curr[2] + 1;
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, curr[2] + 1});
                }
            }
        }
        return -1;
    }
}
      
var cutOffTree = function(forest) {
    const rows = forest.length, cols = forest[0].length;
    let trees = [];
    for (let r = 0; r < rows; ++r)
        for (let c = 0; c < cols; ++c)
            if (forest[r][c] > 1)
                trees.push([forest[r][c], r, c]);
    trees.sort((a, b) => a[0] - b[0]);

    function bfs(sr, sc, tr, tc) {
        if (sr === tr && sc === tc) return 0;
        let visited = Array.from({length: rows}, () => Array(cols).fill(false));
        let queue = [[sr, sc, 0]];
        visited[sr][sc] = true;
        let dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        while (queue.length) {
            let [r, c, d] = queue.shift();
            for (let [dr, dc] of dirs) {
                let nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && forest[nr][nc] !== 0) {
                    if (nr === tr && nc === tc) return d + 1;
                    visited[nr][nc] = true;
                    queue.push([nr, nc, d + 1]);
                }
            }
        }
        return -1;
    }

    let sr = 0, sc = 0, total_steps = 0;
    for (let [_, tr, tc] of trees) {
        let steps = bfs(sr, sc, tr, tc);
        if (steps === -1) return -1;
        total_steps += steps;
        sr = tr; sc = tc;
    }
    return total_steps;
};

Problem Description

The "Cut Off Trees for Golf Event" problem presents you with a 2D grid forest where each cell contains:

  • 0: an obstacle (cannot walk through)
  • 1: empty ground (can walk through)
  • >1: a tree with a positive integer representing its height
You start at position (0, 0). The goal is to cut all trees in order of increasing height (from the shortest to the tallest). You can only move up, down, left, or right to adjacent cells that are not obstacles. After cutting a tree, the cell becomes ground (1).
The task is to return the minimum total number of steps required to cut all the trees in the specified order. If it is impossible to reach any tree, return -1.
Constraints:
  • Each tree must be cut in order of increasing height.
  • You may not cut a tree out of order or skip trees.
  • Obstacles cannot be traversed.
  • There is always at least one cell with value >1.

Thought Process

At first glance, the problem seems to require finding a path through a grid, cutting trees as you go. The naive approach might be to try all possible orders or paths, but the problem states we must cut trees in order of increasing height. This constraint greatly simplifies the problem and allows us to plan our approach.
The main challenge becomes: for each tree (in order), what is the shortest path from our current position to the tree's position? Since obstacles may block access to some trees, we must check reachability for each tree before attempting to cut it.
The brute-force approach would be to use depth-first search (DFS) for each tree, but this would be inefficient for large grids. Instead, we can use breadth-first search (BFS) to find the shortest path between two points in a grid, which is optimal for unweighted graphs.
The key realization is that we can process each tree one by one, always moving from our current position to the next tree in sorted order, using BFS for each movement.

Solution Approach

We can break down the solution into several clear steps:

  1. Identify all trees: Iterate through the grid and collect all cells with a value greater than 1. Store their positions and heights.
  2. Sort the trees: Since we must cut trees in increasing order of height, sort the list of trees based on their heights.
  3. Iterate through the sorted trees: For each tree in the sorted list:
    • Use BFS to find the shortest path from the current position to the tree's position.
    • If the tree is unreachable (BFS returns -1), return -1 immediately.
    • If reachable, add the number of steps to a running total, and update the current position to the tree's position.
  4. Return the total steps: After all trees have been cut, return the total number of steps taken.
Why BFS? BFS is used because it finds the shortest path in an unweighted grid. For each movement between trees, we only care about the minimum number of steps, not the actual path.
Why not precompute all paths? The grid changes as trees are cut (cells become 1), but since we only cut trees in increasing height, we can safely update the grid after each tree is cut.

Example Walkthrough

Sample Input:
forest = [ [1,2,3], [0,0,4], [7,6,5] ]

Step 1: Collect and sort trees

  • Trees (height, row, col): (2,0,1), (3,0,2), (4,1,2), (5,2,2), (6,2,1), (7,2,0)
  • Sorted order: (2,0,1) → (3,0,2) → (4,1,2) → (5,2,2) → (6,2,1) → (7,2,0)
Step 2: Move and cut each tree in order
  • Start at (0,0). Move to (0,1): 1 step (cut tree 2).
  • Move from (0,1) to (0,2): 1 step (cut tree 3).
  • Move from (0,2) to (1,2): 1 step (cut tree 4).
  • Move from (1,2) to (2,2): 1 step (cut tree 5).
  • Move from (2,2) to (2,1): 1 step (cut tree 6).
  • Move from (2,1) to (2,0): 1 step (cut tree 7).
Total steps: 1 + 1 + 1 + 1 + 1 + 1 = 6
Result: 6
At each step, BFS finds the shortest valid path, and the process continues until all trees are cut.

Time and Space Complexity

Brute-Force Approach:
If we tried all possible orders, complexity would be factorial in the number of trees, which is infeasible.
Optimized BFS Approach:

  • Let T be the number of trees, R and C the grid dimensions.
  • For each tree, we perform a BFS that may visit all R*C cells in the worst case.
  • Total time complexity: O(T * R * C)
  • Space complexity: O(R * C) for the BFS queue and visited array.
This is efficient for the grid sizes allowed by the problem.

Summary

The "Cut Off Trees for Golf Event" problem is elegantly solved by:

  • Sorting all trees by height
  • Using BFS to find the shortest path to each successive tree
  • Accumulating the step count and returning -1 if any tree is unreachable
The key insight is that BFS ensures shortest paths in an unweighted grid, and sorting the trees eliminates the need for permutations. This makes the solution both efficient and easy to understand.