1697 Checking Existence of Edge Length Limited Paths

1697. Checking Existence of Edge Length Limited Paths Idea This problem at first looks a lot like a shortest path problem, but the test case size(\(10^5\)) seems to be too big. Another observation is that the problem doesn’t really ask for shortest path, instead it asks if the max weight along the path is smaller than something, (hopefully) this relaxes the problem a little bit. As there is no easy way to find out the max path weight given two random nodes in the graph(probably just DFS and BFS, which result in \(n^2\) time complexity, Floyd-Warshall algorithm has \(n^3\)), we try something else....

April 29, 2023 · mimimi

133 Clone Graph

133. Clone Graph My last AC submission was in May 2022, almost one year has passed and fk my memory about this problem has gone too. 🥲 My first intuition was nearly correct (DFS and clone along the way), however, I messed up with some details. Then I came up with the first approach below… Not fast but quite easy to understand. First Approach General Idea The complicated part about this problem is how do we avoid going into a loop and make sure we cover every edge in the cloned graph....

April 8, 2023 · mimimi

1101 the Earliest Moment When Everyone Become Friends

Union Find with a counter that does count-- when there is a successful union, when the count reach 1 (everything is connected) return the timestamp Trick: remember to sort by timestamp

March 19, 2023 · mimimi