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.
Ah...the struggle continues, another day another DP problem to humble and humiliate me at the same time :D
Overthinking and misunderstanding the problem is our true enemy, we must be constantly on guard so they don't push us down the abyss of wasting life forever...
This problem is probably medium of medium problems. from the problem description and the images provided in the explanation, you should see that this is basically a tree problem, like a min path tree problem. Pretty sure there is one leetcode question in the tree form but I am not up for that search after this tragedy.
Once you see that this is a tree path problem, you should be able to see that BFS or DFS would be your best friend! I went with DFS, and this is apparently this is already a mistake, I'll explain later.
So the DFS will proceed with 3 children: left, middle, right. Then we will just return the minimum of the 3 plus the value of the current node.
Finally to make things faster we have to memoize, the true essence of a DP problem. Luckily for this problem we can just use the row and col number as the key to memorize what is the minimum path from the bottom up.
Below is my code that didn't pass for some reason:
var minFallingPathSum = function(matrix) {
//so this is a tree problem, the matrix is the tree.
//we are to find the minimum sum of all possible paths
const memo = {};
const total = [];
for (let col=0; col < matrix[0].length; col++ ) {
total.push(recurr(0, col));
};
function recurr (row, col) {
const key = `${row},${col}`;
if(memo[key]) return memo[key]
if(row >= matrix.length) return null;
if(col >= matrix[0].length) return null;
if(col < 0) return null;
const available = [
recurr(row+1, col-1), //left
recurr(row+1, col), //middle
recurr(row+1, col+1), //right
].filter(Boolean);
const min = available.length ? Math.min(...available) : 0;
const val = matrix[row][col] + min;
memo[key] = val;
return val;
}
return Math.min(...total);
};
can you spot the bug ? For the ones who have suffered more than I have should be able to see that the demon in this problem is .filter(Boolean), because of 0 values. I did not think of this when I had this solution and thought that the problem was that the greedy solution isn't viable. Therefore instead of Math.min of the current iteration, I should memoize everything and Math.min on the final giant array:
var minFallingPathSum = function(matrix) {
//so this is a tree problem, the matrix is the tree.
//we are to find the minimum sum of all possible paths
const memo = {};
let total = [];
for (let col=0; col < matrix[0].length; col++ ) {
total = total.concat(
recurr(0, col)
);
};
function recurr (row, col) {
const key = `${row},${col}`
if(memo[key]) {
return memo[key];
}
if(row >= matrix.length) return;
if(col >= matrix[0].length) return;
if(col < 0) return;
const val = matrix[row][col]
const children = []
.concat(recurr(row+1, col-1)) //left
.concat(recurr(row+1, col)) //middle
.concat(recurr(row+1, col+1)) //right
.filter(a => a !== undefined);
if(!children.length) {
return [val];
}
const vals = children.map(function(currentSum){
return currentSum + val
})
if(row!=0) memo[key] = [Math.min(...vals)];
return Math.min(...vals);
}
return Math.min(...total);
};
well well, would you look at that ... BASICALLY THE SAME FUCKING CODE EXCEPT IT RETURNS AN ARRAY! Oh can you feel my pain... the code just above is the result of probably 4 hours... 4 hours of running around like a chicken without head. It is only after I went back to my first code that I realized the bug was really the .filter ... at least it's better than a missing semicolon right ? ... haha ...
(honestly though this solution probably could be fine with the interviewer, having a 99.9% solution is much better than anything else that could happen during that chaos)
Below is the optimum code:
const minFallingPathSum = function(matrix) {
const m = matrix.length, n = matrix[0].length;
for (let i = 1; i < m; i++) {
for (let j = 0; j < n; j++) {
matrix[i][j] = Math.min(
matrix[i - 1][j],
matrix[i - 1][j - 1] || 101,
matrix[i - 1][j + 1] || 101
) + matrix[i][j];
}
}
return Math.min(...matrix[m - 1]);
};
I guess it's good that this problem hurts me so bad, otherwise I would probably never see the difference between DFS and BFS really.
DFS works like this:
1
12
123
the numbers are nodes, as you can see, the path grows bigger as we go down each level more
BFS:
12
12
1
Notice that the BFS does not increase the problem space per level. This is the significant difference that makes the BFS much faster than my DFS solution.
When you look at the code, proceed level by level and instead by the one specific path, you'll see that we finish finding the minimum path for each node at the same level and memoize that minimum value at respective node. Therefore the solution is a proper implementation of Dijkstra's shortest path algorithm. BURNING THIS TO MY MIND RIGHT NOW (although maybe the interviewer would push me to Dijkstra's the moment I opted for the DFS?).
the lessons here:
1.) good job noticing this is a tree problem
2.) REMEMBER that shortest path problem will probably require Dijkstra's you dumb dumb.
3.) BFS may be better than DFS when it comes to limiting space complexity
4.) fucking .filters(Boolean) ... with ints
5.) .concat super helpful with eliminating nested array, could be handy in future problems
Gonna be trying to lift my depression now :) See you in a couple of dark hours!
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)