01 Matrix on LeetCode: Multi-Source BFS and Two-pass DP Solution

In Multi-source BFS, we start from multiple source nodes simultaneously instead of starting from a single source node, In this case, all the 0 cells act as the initial sources, and we expand outward in all directions. This works efficiently because BFS inherently explores all nodes layer by layer, guaranteeing that the first time we reach a cell, it is via the shortest possible path. Unlike the naive approach of running BFS separately for each 1 cell (which would be too slow), multi-source BFS spreads out from all 0s in parallel. Again, BFS processes each cell exactly once so this solution will run in O(m*n). As of the DP solution, the recursive approach must NOT create cyclic dependencies. When we are computing the distance for a cell, we are making recursive calls to all its neighbors, right?. But if two cells depend on each other, for example, cell A calls cell B, which in turn calls cell A (or another cell that eventually calls A) before A’s value is finalized, you’ll end up in an infinite loop or incorrect results because the dp value for A is still set to –1 when B checks it. In recursive DP, if we do not ensure that all dependent subproblems are solved before the current cell’s computation, the recursion can “chase its tail” or run infinitely and never reach a stable solution. Read More

Impermanence

For days now, a strange sensation has taken root in me. It is as if I have been shot somehow, and blood is gushing through the gaps of my fingers in an unrelenting endless flow, without pause, without mercy, without any haste or hesitation, but with a measured, inevitable grace. And I can’t stop it in no means. It does not pool or clot, it simply leaves, abandoning the very me, slipping from each corridors of my body. Read More

Tech To Be Obsoleted

My suggestion for novice PC users who are thinking of building a PC for causal usage is to avoid online PC builder hobbyists. Most PC builders community online are often some too-enthusiastic people out there who are more into keeping the latest-fastest-unnecessarily_overclocked PC in one corner of their room. It’s their HOBBY (not necessity) to squeeze every hz of their processor & other components often completely unnecessarily only to waste their time gaming and commenting on their communities :v So get whatever is decent for your workload and don’t chase for the someday-i-might-need-this-feature or the never-obsolete-PC. No tech is future-proof. It will start becoming obsolete or at least old in terms of technology even before you realize it, but most probably it will keep working and you will not upgrade it until it REALLY sucks – it is when it can’t do what you NEED to do. Most potato users build a PC maybe once a decade unlike these hobbyists so know that you are not on the same ground as the people you are taking advice from. Read More

Dungeon Game on LeetCode : Finding The Right Question To Ask in DP Problems

I have been solving DP problems for last 2 days and guess what, they are really cooool and fun to solve. Previously I didn’t enjoy this much while solving topic-wise problems on Prefix Sum or Sliding Window. Dungeon Game is my first solved bottom-up DP problem. It’s marked as hard, but I believe it is sort of quite medium level problem.

In DP problems, the main part is to find out what to remember as Errichto said. And for that, you have to know the right question to ask.

Read More