Skip to main content
Talentd

Cut Off Trees for Golf Event - Solution & Explanation

HardArrayBreadth-First SearchHeap (Priority Queue)Matrix22 min readAsked at: Amazon, Flipkart
Practice this problem

Problem Statement

You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an m x n matrix. In this matrix:

  • 0 means the cell cannot be walked through.
  • 1 represents an empty cell that can be walked through.
  • A number greater than 1 represents a tree in a cell that can be walked through, and this number is the tree's height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes 1 (an empty cell).

Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.

Note: The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.

 

Example 1:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

Example 2:

Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.

Example 3:

Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
Explanation: You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.

 

Constraints:

  • m == forest.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 109
  • Heights of all trees are distinct.

Approach Overview

Problem Overview: You are given a grid representing a forest. Cells contain obstacles (0), walkable ground (1), or trees with heights greater than 1. Starting at (0,0), you must cut all trees in increasing order of height while minimizing total steps. If any tree is unreachable, return -1.

Approach 1: BFS Shortest Path Between Trees (Time: O(T * m * n), Space: O(m * n))

The key idea is to cut trees strictly in increasing height order. First collect all tree cells and sort them by height (often using a heap or sorted list). Starting from (0,0), run BFS to compute the shortest path to the next tree. After reaching it, repeat BFS from that position to the next tree in sorted order. Each BFS explores the grid level-by-level using a queue and a visited set to avoid revisiting cells.

This works because the grid has uniform movement cost, so Breadth-First Search always finds the shortest path. Tree ordering can be managed with sorting or a Heap (Priority Queue). In the worst case you run BFS for every tree, giving O(T * m * n) time where T is the number of trees. The grid itself is a classic matrix traversal problem.

Approach 2: Bidirectional BFS for Optimal Path Finding (Time: O(T * m * n), Space: O(m * n))

Bidirectional BFS speeds up individual shortest-path searches by exploring from both the start and target tree simultaneously. Instead of expanding one frontier across the entire grid, two frontiers grow toward each other. When they meet, you have the shortest distance. This reduces the explored search space in practice, especially when trees are far apart.

The algorithm still processes trees in sorted height order, but each step uses two queues and two visited sets. The theoretical worst-case complexity remains O(T * m * n), but the constant factor is lower because each BFS explores fewer cells on average. This approach is useful when the forest grid is large and paths between trees are long.

Recommended for interviews: The standard BFS shortest-path approach is what most interviewers expect. It shows you recognize the grid as an unweighted graph and know how to combine sorting with repeated BFS searches. Bidirectional BFS is a strong optimization discussion if the interviewer asks about improving practical performance.

Approach 1: Breadth-First Search (BFS) for Shortest Path

This approach involves using a BFS algorithm to find the shortest path between the starting point and each tree in increasing order of their heights. We first list all trees with their positions and heights, sort them, and for each sorted tree, compute the shortest path using BFS. If any tree is unreachable, we return -1.

This C solution first uses BFS to calculate the shortest path between trees, starting from (0, 0) and moving to trees in increasing order of their height. The binary search is used to sort the trees based on their height first. If any tree is unreachable during a BFS computation, the function returns -1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of this approach is O(T * m * n) where T is the number of trees. This is because we perform BFS from the starting position to each tree. The space complexity is O(m * n) due to the storage of the queue and visited matrix in BFS.

Try this approach in the editor β†’

Approach 2: Bidirectional BFS for Optimal Path Finding

Using Bidirectional BFS can help in optimizing the pathfinding step by searching from both the start and the goal concurrently. The aim is to decrease the search space substantially as the two searches meet in the middle. This method is an extension to the regular BFS approach, potentially optimizing the traversal cost considerably under specific configurations.

A detailed explanation of handling bidirectional BFS in C would involve structuring two queues for the forward and backward search, ensuring efficient state management overlaps and transitions by interfacing node positions from both directions dynamically, essentially shortening the BFS travel path.

Code

CC++Python

C

C++

Python

Complexity

The potential benefits of bidirectional search in space complexity can be realized when effectively reducing the number of explored nodes, as time complexity ideally shortens from O(b^d) to roughly O(b^(d/2)), where b is the branching factor and d the solution depth.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) for Shortest Path

The time complexity of this approach is O(T * m * n) where T is the number of trees. This is because we perform BFS from the starting position to each tree. The space complexity is O(m * n) due to the storage of the queue and visited matrix in BFS.

Bidirectional BFS for Optimal Path Finding

The potential benefits of bidirectional search in space complexity can be realized when effectively reducing the number of explored nodes, as time complexity ideally shortens from O(b^d) to roughly O(b^(d/2)), where b is the branching factor and d the solution depth.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS Shortest Path Between TreesO(T * m * n)O(m * n)General solution for grid shortest paths where movement cost is uniform
Bidirectional BFSO(T * m * n)O(m * n)When start and target are far apart and you want faster practical performance

Video Solution

θŠ±θŠ±ι…± LeetCode 675. Cut Off Trees for Golf Event - εˆ·ι’˜ζ‰Ύε·₯作 EP55 β€’ Hua Hua β€’ 7,515 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Cut Off Trees for Golf Event easy or hard?
Cut Off Trees for Golf Event is classified as Hard on LeetCode. The difficulty comes from combining multiple concepts: sorting targets, repeatedly computing shortest paths in a matrix, handling unreachable cells, and optimizing BFS traversal across the grid.
Cut Off Trees for Golf Event Python/Java solution
Most implementations follow the same pattern across languages. First collect and sort all trees by height, then run BFS from the current position to each tree sequentially. Python typically uses collections.deque for BFS, while Java uses a Queue such as ArrayDeque.
How to solve Cut Off Trees for Golf Event in O(n)?
The problem cannot be solved in strict O(n) because multiple shortest-path searches are required across the grid. The optimal practical approach sorts trees and performs BFS between them, resulting in O(T * m * n) time. Bidirectional BFS can reduce explored nodes but does not change the worst-case complexity.
What is the best approach for Cut Off Trees for Golf Event?
The most reliable approach is sorting trees by height and running Breadth-First Search (BFS) between consecutive trees. BFS guarantees the shortest path in an unweighted grid. The algorithm repeatedly finds the shortest path from the current position to the next smallest tree, giving overall time complexity of O(T * m * n).
Is Cut Off Trees for Golf Event asked at Google/Amazon/Meta?
Cut Off Trees for Golf Event is considered a hard grid traversal problem that tests BFS, graph modeling, and pathfinding. Variants of shortest-path grid problems frequently appear in interviews at companies like Amazon, Google, and Meta because they evaluate graph reasoning and algorithm optimization.
What data structure is used in Cut Off Trees for Golf Event?
The main data structures are a queue for BFS traversal, a visited set or matrix to avoid revisiting cells, and a sorted list or heap (priority queue) to process trees in increasing height order. The grid itself is treated as a graph where each cell connects to its four neighbors.
What is the time complexity of Cut Off Trees for Golf Event?
The typical solution runs BFS for each tree after sorting them by height. If the grid size is m Γ— n and there are T trees, each BFS can visit up to m*n cells. The total time complexity is O(T * m * n), with space complexity O(m * n) for the queue and visited structure.

Ready to solve this problem?

Practice Cut Off Trees for Golf Event with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays