LeetCode 675: Cut Off Trees with BFS, A* & Union-Find Optimization

Career Anecdote: Background Check Failure

A candidate passed multiple interview rounds at a large company but failed the background check. The salary bank statement for July showed 1,000+ yuan more than the resume stated. The candidate explained they had worked at a new company for only 5 days, completed training, found it unsuitable, left without social insurance contributions, and therefore omitted it from the resume. HR viewed the omission as a red flag: the candidate did not disclose the short stint proactively, and a 5-day departure raised stability concerns, possibly indicating a "stepping stone" job. With multiple candidates in the pipeline and background check costs, the company terminated the process.

Problem Statement: LeetCode 675 Cut Off Trees for Golf Event

Given an m x n matrix forest where: 0 = obstacle (impassable) 1 = ground (walkable) >1 = tree (walkable, value = height)

Start at (0,0). Move up/down/left/right one cell per step. Must cut trees in strictly increasing height order (all heights unique). Cutting a tree turns its cell to 1. Return minimum total steps to cut all trees, or -1 if impossible.

Basic Analysis

Two key properties:

Unique cutting order: Sort all tree cells by height ascending; this sequence is fixed.

Shortest paths are static: Cutting a tree only changes its cell from >1 to 1 (ground), never to an obstacle. Thus the shortest path between any two cells never increases during the process.

Therefore, the total minimum steps equals the sum of shortest-path distances between consecutive trees in the sorted list (including from start (0,0) to the first tree).

BFS Solution

Constraints: m, n <= 50, edge weight = 1. BFS finds shortest path between two points in O(mn). With up to mn trees, total complexity O((mn)^2) ≈ 6.25e6 operations, well within limits.

Algorithm:

Scan grid, collect all trees as (height, x, y) triples.

Sort by height ascending.

If forest[0][0] == 0, return -1.

For each consecutive pair (including start), run BFS to get distance d. If any BFS returns -1, return -1. Accumulate d.

class Solution { int N = 50; int[][] g = new int[N][N]; int n, m; List<int[]> list = new ArrayList<>(); public int cutOffTree(List<List<Integer>> forest) { n = forest.size(); m = forest.get(0).size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { g[i][j] = forest.get(i).get(j); if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j}); } } Collections.sort(list, (a,b)->a[0]-b[0]); if (g[0][0] == 0) return -1; int x = 0, y = 0, ans = 0; for (int[] ne : list) { int nx = ne[1], ny = ne[2]; int d = bfs(x, y, nx, ny); if (d == -1) return -1; ans += d; x = nx; y = ny; } return ans; } int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; int bfs(int X, int Y, int P, int Q) { if (X == P && Y == Q) return 0; boolean[][] vis = new boolean[n][m]; Deque<int[]> d = new ArrayDeque<>(); d.addLast(new int[]{X, Y}); vis[X][Y] = true; int ans = 0; while (!d.isEmpty()) { int size = d.size(); while (size-- > 0) { int[] info = d.pollFirst(); int x = info[0], y = info[1]; for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == 0 || vis[nx][ny]) continue; if (nx == P && ny == Q) return ans + 1; d.addLast(new int[]{nx, ny}); vis[nx][ny] = true; } } ans++; } return -1; } }

Complexity: Preprocessing O(mn), sorting O(k log k) ( k = tree count), each BFS O(mn), total O(k * mn). Space O(mn).

A* Algorithm

BFS explores uniformly in four directions. A* uses a heuristic to prioritize promising directions. For grid with unit edges, Manhattan distance h = |x1-x2| + |y1-y2| is admissible (never overestimates true distance).

Key insight: The priority queue orders by f = g + h where g = actual steps from start, h = Manhattan to target. When a node's g improves, it must be re-inserted into the queue because A* only guarantees optimal

g</sub> for the target node when popped; other nodes may need updates.</p><pre><code>int astar(int X, int Y, int P, int Q) { if (X == P && Y == Q) return 0; Map<Integer, Integer> map = new HashMap<>(); PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]); q.add(new int[]{f(X, Y, P, Q), X, Y}); map.put(getIdx(X, Y), 0); while (!q.isEmpty()) { int[] info = q.poll(); int x = info[1], y = info[2], step = map.get(getIdx(x, y)); for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny); if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == 0) continue; if (nx == P && ny == Q) return step + 1; if (!map.containsKey(nidx) || map.get(nidx) > step + 1) { q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny}); map.put(nidx, step + 1); } } } return -1; } int f(int X, int Y, int P, int Q) { return Math.abs(X - P) + Math.abs(Y - Q); } int getIdx(int x, int y) { return x * m + y; }

Note: The condition map.get(nidx) > step + 1 ensures re-queueing when a shorter path to an intermediate node is found.

A* + Union-Find Pre-check for Unreachable Cases

In scenarios where the target is geometrically close but blocked by obstacles (e.g., target to the right but path requires a long leftward detour), A* may expand many nodes before discovering the detour, adding a log factor from the priority queue. A cheap pre-check using Union-Find (Disjoint Set Union) can detect disconnected components early. Method: During initial grid scan, union each non-obstacle cell with its left and upper neighbors (avoids duplicate unions). After building DSU, verify every tree cell is connected to (0,0) . If any tree is disconnected, return -1 immediately.

class Solution { int N = 50; int[][] g = new int[N][N]; int n, m; int[] p = new int[N * N + 10]; List<int[]> list = new ArrayList<>; void union(int a, int b) { p[find(a)] = p[find(b)]; } boolean query(int a, int b) { return find(a) == find(b); } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int getIdx(int x, int y) { return x * m + y; } public int cutOffTree(List<List<Integer>> forest) { n = forest.size(); m = forest.get(0).size(); for (int i = 0; i < n * m; i++) p[i] = i; int[][] tempDirs = {{0,-1},{-1,0}}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { g[i][j] = forest.get(i).get(j); if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j}); if (g[i][j] == 0) continue; for (int[] di : tempDirs) { int nx = i + di[0], ny = j + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] != 0) union(getIdx(i, j), getIdx(nx, ny)); } } } for (int[] info : list) { int x = info[1], y = info[2]; if (!query(getIdx(0, 0), getIdx(x, y))) return -1; } Collections.sort(list, (a,b)->a[0]-b[0]); int x = 0, y = 0, ans = 0; for (int[] ne : list) { int nx = ne[1], ny = ne[2]; int d = astar(x, y, nx, ny); if (d == -1) return -1; ans += d; x = nx; y = ny; } return ans; } // astar, f, getIdx same as above }

The DSU pre-processing adds O(mn α(mn)) time, negligible compared to potential wasted A* searches on unsolvable instances.