This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question is hard ... but I also misunderstood the problem and made it even harder than it is lol...hahhaahahahahahahahahhahaha fuck me

Given a 2d array of integers representing tree height, find the minimum steps required to cut down all of the trees from the smallest to the biggest tree.

You start from [0,0]. You can only walk up left right down.

a cell of 0 = unwalkable
a cell of 1 = no tree/cut tree and can be travelled
a cell of >1 = a tree of height equal to the value, it can also be walked through as well.

Since we cut from smallest to biggest, we should sort first.

Once we have the sort, we start from 0,0 and travel to the smallest tree and cut it. Then from that smallest tree position, we go to the next smallest. This continues until all trees are cut or you cannot find the next tree (this happens when you have a wall of 0s, which then you return -1).

To do this, we have to keep in mind that the problem requires the minimum number of steps to finish. This means that we have to do BST instead of DFS. BST always gives the minimum travel distance from node A to node B.

The one thing to remember is that after you cut a tree, you have to reset the visited map so that we can walk back to get to the next tree.

the code is below:

var cutOffTree = function(forest) {
    const trees = [];
    for (let row = 0; row < forest.length; row ++ ) {
        for (let col = 0; col < forest[0].length; col++ ) {
            if(forest[row][col] >1) trees.push(forest[row][col])
        }
    };    
    trees.sort(function(a,b){ return a > b ? 1 : -1});

    let count = 0;
    let found;
    let startPosition = [0,0];
    let visited = {};
    let key, current;
    let row, col
    let stack = [];
    let nextStack = []
    let target

    for (let i=0; i <trees.length; i++) {
        target = trees[i]
        visited = {};
        nextStack = [startPosition];
        count--; //so we don't count the starting position of each iteration

        while (nextStack.length && !found) {
           stack = nextStack;
           nextStack = [] 
           count++;
           for (let j=0; j <stack.length; j++) {
                [row, col] = stack[j];
                key = `${row}:${col}`;

                if(!forest[row] || !forest[row][col]) continue
                if(found || visited[key]) continue;

                visited[key] = true;
                current = forest[row][col];

                if(current === target) {
                    found = true;
                    startPosition = [row,col];
                    break;
                } else {
                    nextStack.push([row+1, col]);
                    nextStack.push([row-1, col]);
                    nextStack.push([row, col+1]);
                    nextStack.push([row, col-1]);
                }
            };

        }

        if(!found) return -1;
        found = false;
    };

    return count;
};

The for while for loop looks scary, but it really isn't.
first for loop is to iterate through the trees to cut, completely unavoidable.
The while loop is to keep the BST going after each level of iteration, so we'd know when to increment the count.
The second for loop is the actual BST.

So the logic of the solution goes like this:
1.) sort trees
2.) iterate through the trees
3.) for each target tree we cut, we start from startPosition
4.) we check each of the current level position in the BFS

if a position matches, we break out of the while-for loop for the BFS and start again for the next target tree

else we add the current cell's up down left right to the nextStack

we continue BFS until all of current level is done
if all current level down, then the while loop rehydrates the stack from the nextStack; we also add 1 to the counter to signal an additional step of travel is necessary.

if both stack and nextStack are empty, then we know a tree wasn't found and we return -1;

I think this question is reasonable for the given level indicator. My solution seems fine to me but its performance is terrible. I don't know why honestly since it's comparable to this

I've asked online about my code problem, if there is an update I'll document it here, if you know what's wrong with mine, PPPPPPPLEASE comment below.

Let me know anything on your mind after reading through this, THANKS!