LeetCode 675 - Cut Off Trees for Golf Event

LeetCode Problem 675

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Heap (Priority Queue), Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid representing a forest. Every cell contains one of three possible values:

• 0 means the cell is blocked and cannot be entered.
• 1 means the cell is empty and can be walked through.
• Any value greater than 1 represents a tree, and the value itself is the tree's height.

We start at position (0, 0) and must cut down every tree in strictly increasing order of height. After a tree is cut, that cell becomes a normal walkable cell with value 1.

The goal is to compute the minimum total number of steps required to cut all trees in the required order. If even one tree cannot be reached, we must return -1.

The movement rules are important. From any position, we may move only one step at a time in the four cardinal directions:

• Up
• Down
• Left
• Right

Diagonal movement is not allowed.

The constraints are relatively small:

• m, n <= 50
• The grid contains at most 2500 cells.

This immediately suggests that graph traversal algorithms such as Breadth First Search are feasible. Since every movement has equal cost, BFS is the ideal shortest path algorithm here.

Another important observation is that trees must be cut in sorted order by height. The problem guarantees all tree heights are unique, which means there is exactly one valid cutting order.

Several edge cases are important:

• The starting cell itself may contain a tree.
• Some trees may be completely isolated by obstacles.
• The forest may contain many trees requiring repeated shortest path computations.
• A naive global pathfinding strategy could become very inefficient if shortest paths are recomputed poorly.
• The shortest route between two trees may require walking through cells containing taller trees that have not yet been cut. This is allowed because all nonzero cells are walkable.

Approaches

Brute Force Approach

The brute force idea is to try all possible paths between trees while maintaining the required cutting order.

We first sort all trees by height. Then, for every pair of consecutive targets, we attempt to enumerate every possible route from the current position to the next tree and choose the shortest valid one.

This approach is correct because examining every possible route guarantees we eventually find the minimum distance between each pair of trees. Summing those minimum distances gives the optimal total path length.

However, this is computationally infeasible. The number of possible paths in a grid grows exponentially with path length. Even for moderate grid sizes, enumerating all paths becomes impossible.

Optimal Approach

The key observation is that the problem naturally decomposes into multiple shortest path problems on an unweighted grid.

Since every movement costs exactly one step, Breadth First Search computes the shortest path between two positions efficiently.

The algorithm becomes:

1. Collect all trees.
2. Sort them by height.
3. Starting from (0, 0), repeatedly run BFS to the next tree.
4. Add the shortest distance to the answer.
5. Move to that tree's position and continue.

If any BFS fails to reach its target, return -1.

This works efficiently because:

• The grid size is small enough for repeated BFS traversals.
• BFS guarantees shortest paths in unweighted graphs.
• Tree ordering is fixed and deterministic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates many possible paths between trees
Optimal	O((mn)^2)	O(mn)	Uses BFS between consecutively sorted trees

Algorithm Walkthrough

1. Traverse the entire forest and collect every tree.

A tree is any cell with value greater than 1. For each tree, store its height and coordinates. We need the coordinates for pathfinding and the height for sorting. 2. Sort all trees by height.

Since trees must be cut in increasing order, sorting determines the exact sequence we must follow. 3. Initialize the current position as (0, 0).

This is our starting point before cutting any trees. 4. For each tree in sorted order, run BFS from the current position to the tree.

BFS is ideal because:

• Every edge has equal weight.
• We need the shortest number of moves.
• The grid can be modeled as an unweighted graph.

5. During BFS, maintain:

• A queue for level order traversal.
• A visited set or matrix to avoid revisiting cells.
• Distance information through BFS levels.

6. From each cell, attempt movement in four directions.

Only move into cells that:

• Stay within bounds.
• Are not blocked (forest[r][c] != 0).
• Have not been visited yet.

7. If BFS reaches the target tree, return the shortest distance.

BFS guarantees the first time we reach the target is the minimum number of steps. 8. If BFS exhausts all reachable cells without finding the target, return -1.

This means the tree cannot be reached. 9. Add the BFS distance to the total answer.

Then update the current position to the newly cut tree. 10. Continue until all trees are processed. 11. Return the accumulated total distance.

Why it works

The correctness relies on two properties.

First, trees must be cut in strictly increasing height order, so the sequence of targets is fixed. There is no optimization choice regarding which tree to visit next.

Second, BFS always computes the shortest path in an unweighted graph. Since each movement costs exactly one step, the BFS distance between consecutive trees is optimal.

Combining these two facts guarantees the sum of all BFS distances is the minimum total number of steps required.

Python Solution

from collections import deque
from typing import List

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        rows = len(forest)
        cols = len(forest[0])

        trees = []

        for r in range(rows):
            for c in range(cols):
                if forest[r][c] > 1:
                    trees.append((forest[r][c], r, c))

        trees.sort()

        def bfs(start_row: int, start_col: int,
                target_row: int, target_col: int) -> int:

            if start_row == target_row and start_col == target_col:
                return 0

            queue = deque([(start_row, start_col, 0)])
            visited = {(start_row, start_col)}

            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            while queue:
                row, col, distance = queue.popleft()

                for dr, dc in directions:
                    next_row = row + dr
                    next_col = col + dc

                    if (
                        0 <= next_row < rows
                        and 0 <= next_col < cols
                        and forest[next_row][next_col] != 0
                        and (next_row, next_col) not in visited
                    ):
                        if next_row == target_row and next_col == target_col:
                            return distance + 1

                        visited.add((next_row, next_col))
                        queue.append(
                            (next_row, next_col, distance + 1)
                        )

            return -1

        total_steps = 0
        current_row = 0
        current_col = 0

        for _, tree_row, tree_col in trees:
            distance = bfs(
                current_row,
                current_col,
                tree_row,
                tree_col
            )

            if distance == -1:
                return -1

            total_steps += distance
            current_row = tree_row
            current_col = tree_col

        return total_steps

The implementation begins by scanning the grid and collecting all tree cells into the trees list. Each entry stores the tree height together with its coordinates.

The trees are then sorted so they are processed in the required order.

The nested bfs function computes the shortest path between two positions. It uses a queue for level order traversal and a visited set to avoid revisiting cells.

For each position removed from the queue, the algorithm explores the four adjacent cells. Only valid, nonblocked, unvisited cells are added to the queue.

If the target position is reached, the current shortest distance is returned immediately. If the queue becomes empty first, the target is unreachable and the function returns -1.

The outer loop processes trees sequentially. After each successful BFS, the total step count is updated and the current position moves to the newly cut tree.

If any tree cannot be reached, the algorithm immediately returns -1.

Go Solution

package main

import "container/list"

func cutOffTree(forest [][]int) int {
	rows := len(forest)
	cols := len(forest[0])

	type Tree struct {
		height int
		row    int
		col    int
	}

	trees := []Tree{}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if forest[r][c] > 1 {
				trees = append(trees, Tree{
					height: forest[r][c],
					row:    r,
					col:    c,
				})
			}
		}
	}

	// Simple insertion sort because constraints are small
	for i := 1; i < len(trees); i++ {
		key := trees[i]
		j := i - 1

		for j >= 0 && trees[j].height > key.height {
			trees[j+1] = trees[j]
			j--
		}

		trees[j+1] = key
	}

	bfs := func(startRow, startCol, targetRow, targetCol int) int {
		if startRow == targetRow && startCol == targetCol {
			return 0
		}

		type State struct {
			row      int
			col      int
			distance int
		}

		queue := list.New()
		queue.PushBack(State{
			row:      startRow,
			col:      startCol,
			distance: 0,
		})

		visited := make([][]bool, rows)
		for i := range visited {
			visited[i] = make([]bool, cols)
		}

		visited[startRow][startCol] = true

		directions := [][]int{
			{1, 0},
			{-1, 0},
			{0, 1},
			{0, -1},
		}

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			current := front.Value.(State)

			for _, dir := range directions {
				nextRow := current.row + dir[0]
				nextCol := current.col + dir[1]

				if nextRow >= 0 &&
					nextRow < rows &&
					nextCol >= 0 &&
					nextCol < cols &&
					forest[nextRow][nextCol] != 0 &&
					!visited[nextRow][nextCol] {

					if nextRow == targetRow &&
						nextCol == targetCol {
						return current.distance + 1
					}

					visited[nextRow][nextCol] = true

					queue.PushBack(State{
						row:      nextRow,
						col:      nextCol,
						distance: current.distance + 1,
					})
				}
			}
		}

		return -1
	}

	totalSteps := 0
	currentRow := 0
	currentCol := 0

	for _, tree := range trees {
		distance := bfs(
			currentRow,
			currentCol,
			tree.row,
			tree.col,
		)

		if distance == -1 {
			return -1
		}

		totalSteps += distance
		currentRow = tree.row
		currentCol = tree.col
	}

	return totalSteps
}

The Go implementation follows the same overall structure as the Python version.

One notable difference is the use of container/list to implement the BFS queue. Go does not provide a built in deque structure like Python's collections.deque.

The visited structure is implemented as a two dimensional boolean slice rather than a hash set. This is more memory efficient and faster for fixed grid dimensions.

Go integers are sufficient for this problem because the maximum path length is bounded by the grid size.

Worked Examples

Example 1

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

Sorted trees:

Height	Position
2	(0,1)
3	(0,2)
4	(1,2)
5	(2,2)
6	(2,1)
7	(2,0)

Initial state:

Variable	Value
Current Position	(0,0)
Total Steps	0

Move to tree 2 at (0,1)

BFS path:

(0,0) -> (0,1)

Distance = 1

Variable	Value
Current Position	(0,1)
Total Steps	1

Move to tree 3 at (0,2)

Path:

(0,1) -> (0,2)

Distance = 1

Variable	Value
Current Position	(0,2)
Total Steps	2

Move to tree 4 at (1,2)

Path:

(0,2) -> (1,2)

Distance = 1

Variable	Value
Current Position	(1,2)
Total Steps	3

Move to tree 5 at (2,2)

Path:

(1,2) -> (2,2)

Distance = 1

Variable	Value
Current Position	(2,2)
Total Steps	4

Move to tree 6 at (2,1)

Path:

(2,2) -> (2,1)

Distance = 1

Variable	Value
Current Position	(2,1)
Total Steps	5

Move to tree 7 at (2,0)

Path:

(2,1) -> (2,0)

Distance = 1

Final answer:

6

Example 2

forest = [
    [1,2,3],
    [0,0,0],
    [7,6,5]
]

The middle row completely blocks access to the bottom row.

After reaching tree 3, BFS attempts to reach tree 5 but cannot cross the obstacle row.

The BFS queue eventually becomes empty, so the algorithm returns -1.

Example 3

forest = [
    [2,3,4],
    [0,0,5],
    [8,7,6]
]

The starting position (0,0) already contains the smallest tree.

The first BFS distance is 0 because we are already standing on the tree.

Subsequent moves follow the same structure as Example 1.

Total distance:

0 + 1 + 1 + 1 + 1 + 1 + 1 = 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O((mn)^2)	BFS may traverse the whole grid for each tree
Space	O(mn)	Queue and visited structures may store the entire grid

Let:

• m = number of rows
• n = number of columns
• k = number of trees

Each BFS costs O(mn) because every cell may be visited once.

In the worst case, every cell contains a tree, so k = O(mn).

Therefore, the total complexity becomes:

O(k * mn) = O((mn)^2)

The auxiliary space comes primarily from:

• The BFS queue
• The visited matrix

Both can grow to O(mn) in the worst case.

Test Cases

sol = Solution()

# Example 1
assert sol.cutOffTree([
    [1, 2, 3],
    [0, 0, 4],
    [7, 6, 5]
]) == 6  # standard reachable case

# Example 2
assert sol.cutOffTree([
    [1, 2, 3],
    [0, 0, 0],
    [7, 6, 5]
]) == -1  # unreachable trees

# Example 3
assert sol.cutOffTree([
    [2, 3, 4],
    [0, 0, 5],
    [8, 7, 6]
]) == 6  # starting cell already contains a tree

# Single cell containing a tree
assert sol.cutOffTree([
    [2]
]) == 0  # no movement needed

# Single reachable path
assert sol.cutOffTree([
    [1, 2, 0],
    [1, 3, 4]
]) == 4  # must navigate around obstacle

# Tree blocked immediately
assert sol.cutOffTree([
    [1, 0, 2]
]) == -1  # target cannot be reached

# Multiple trees in straight line
assert sol.cutOffTree([
    [1, 2, 3, 4, 5]
]) == 4  # simple linear traversal

# Large open grid
assert sol.cutOffTree([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]) == 8  # many reachable trees

# Complex obstacle layout
assert sol.cutOffTree([
    [1, 2, 0],
    [0, 3, 4],
    [7, 6, 5]
]) == -1  # disconnected regions

# Minimal empty movement
assert sol.cutOffTree([
    [1, 2]
]) == 1  # one move only

Test	Why
Standard reachable grid	Validates normal BFS traversal
Fully blocked middle row	Verifies unreachable detection
Starting cell is a tree	Ensures zero distance handling
Single cell tree	Tests smallest possible input
Narrow path around obstacles	Validates shortest path computation
Immediately blocked target	Tests impossible path detection
Straight line trees	Verifies simple sequential traversal
Dense tree grid	Stresses repeated BFS operations
Disconnected components	Ensures algorithm stops correctly
One step movement	Tests minimal nonzero distance

Edge Cases

Starting Position Contains a Tree

The starting cell (0,0) may itself contain a tree. This can easily cause bugs if the implementation assumes movement is always required before cutting the first tree.

The implementation handles this naturally because the BFS function immediately returns 0 when the start and target positions are the same.

Unreachable Trees

A tree may be isolated by obstacles. If BFS cannot reach the next target tree, the algorithm must terminate immediately with -1.

This is handled by allowing BFS to exhaust all reachable cells. If the queue becomes empty before reaching the target, the function returns -1, which propagates directly to the final result.

Walking Through Taller Trees

An easy misunderstanding is thinking taller trees block movement until they are cut. This is incorrect. Any nonzero cell is walkable, regardless of tree height.

The implementation correctly checks only:

forest[r][c] != 0

This allows traversal through uncut trees while still enforcing the required cutting order.

Large Number of Trees

In dense forests, nearly every cell may contain a tree. A poor implementation could become inefficient or use excessive memory.

The BFS approach remains efficient because each BFS explores at most the entire grid once, and the maximum grid size is only 50 x 50.