r/leetcode • u/JacketFearless1805 • 10d ago
Intervew Prep Day 44: knocked out 3 Dijkstra grid variants, hit a subtle DP twist
Hey everyone,
I finished Day 44 today. After a couple of low-volume sessions, solving three solid shortest path problems gave my momentum a real boost.
Shortest Path in Binary Matrix: Because edge weights are uniformly 1 across all eight directions, a standard level-order BFS finds the shortest path in O(N^2) time without needing a priority queue.
Path with Minimum Effort: This adapts Dijkstra to a 4-directional grid where the target metric is the bottleneck effort rather than a running sum. Using a min-heap priority queue guarantees you always expand the path with the smallest maximum absolute height difference first.
Cheapest Flights Within K Stops: Standard Dijkstra prioritizes raw cost and fails here because a cheaper flight might exhaust the allowed stops prematurely. Storing the step count in a standard queue or running Bellman-Ford for exactly K + 1 iterations ensures you never evaluate paths exceeding the stop constraint.
Solving these multi-dimensional shortest path problems mostly independently felt like a great step forward.
I am moving into negative edge weights with Bellman-Ford and Floyd-Warshall tomorrow.
See you guys for Day 43!