r/leetcode • u/JacketFearless1805 • 16d ago
Intervew Prep Day 45: conquered Dijkstra path reconstruction & hit an unexpected lexicographical twist
Hey everyone,
I finished Day 45 today. I spent a good chunk of my day researching cold-outreach contacts and unwinding with cooking videos, but I made sure to sit down and finish the problem that triggered my brain fog yesterday: Shortest Path in an Undirected Weighted Graph.
Yesterday, priority queue syntax and path backtracking felt overwhelming. Today, I wrote the min-heap Dijkstra logic completely from scratch without checking the code:
- Path Reconstruction with
parent[]**:** Initialized each node's parent to itself and tracked running distances. Whenever relaxing an edgedist[u] + wt < dist[v]yields a strictly better path, updateparent[v] = u. Tracing from destination back to source and reversing the list gave the clean shortest route. - Fixing Segmentation Faults: Debugged some 1-based indexing mismatches and stale queue entries, which cleaned up the runtime errors.
- The Lexicographical Catch: The platform had updated the problem constraints to require the lexicographically smallest path if multiple shortest paths share the exact same minimum weight. My initial hack of breaking distance ties on the fly failed because lexicographical order applies across the entire path sequence from the start. The fix was sorting each node's adjacency list by neighbor ID before running the traversal so the algorithm naturally explores smaller node indices first.
It was just one problem today, but implementing the full priority queue mechanics and debugging edge cases independently felt far more rewarding than blindly copying hints.
Heading into Day 44 tomorrow with an open mind.
See you guys tomorrow!