Cut Off Trees for Golf Event

HardGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A forest is an m x n grid. A cell with 0 cannot be walked through, a cell with 1 is open ground, and a cell with a value greater than 1 is a tree of that height, which can be walked through too. You start at (0, 0) and must cut down every tree in order from **shortest to tallest**. Each step moves you one cell up, down, left or right. When you stand on a tree's cell you may cut it, and the cell becomes 1. You may walk over trees without cutting them. Return the minimum number of steps needed to cut all trees, or -1 if some tree cannot be reached. All tree heights are distinct, and (0, 0) is never a 0 cell. If (0, 0) holds a tree, it can be cut without moving.

Examples

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Walking right, right, down, down, left, left visits heights 2, 3, 4, 5, 6, 7 in order: 6 steps.
Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
The middle row is blocked, so the bottom trees are unreachable.
Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
The first tree (height 2) is at the start and costs 0 steps; the rest follow as in the first example.

Constraints

  • m == forest.length, n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 10^9
  • Tree heights (values > 1) are distinct
  • forest[0][0] != 0

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems