All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : July 28, 2024
Last updated : July 28, 2024
Related Topics : Breadth-First Search, Graph, Shortest Path
Acceptance Rate : 62.86 %
Once we find the shortest path, the 2nd shortest will at most be that path + a back and forth That, or it'll be a single node more.For the 2nd time reaching the end, it will only use edges that have been traversed either once or twice since all edges have the same weight. We can thus disregard any node visits that have been visited more than twice already to prevent the first instance of a MLE.Instict since we're trying to find the shortest path was to use Dijkstra's and have a heap keep track of it all. This worked, but wasn't the most efficient with a runtime of upwards of 3000ms putting it at the back of the, though still ACed, pack.
Since the edges aren't weighted, i.e. the time from one node to the next is always the same no matter which two nodes, Dijkstra's main advantage / purpose becomes redundant. The constant
$\log{n}$ operations become more damaging than benefitial.Instead, I tried adjusting it to BFS (a very minor adjustment --> just swapping the heapq operations for append with a deque) and it immediately joined the average AC runtime group on the graph (hovering around 1700ms).
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
paths = defaultdict(list)
for u, v in edges :
paths[u].append(v)
paths[v].append(u)
dist1 = [0] + [inf] * n
dist2 = dist1.copy()
# schema: (time when reached, current node no.)
toVisit = [(0, 1)]
while toVisit :
currTime, curr = heapq.heappop(toVisit)
# If first case and second case already found
if dist1[curr] != inf and dist2[curr] != inf :
continue
# Repeat distance
if currTime == dist1[curr] :
continue
# If not found so insert
if dist1[curr] == inf :
dist1[curr] = currTime
else :
dist2[curr] = currTime
# If "red light," adjust time
if currTime % (2 * change) >= change :
nxtTime = currTime + time + change - (currTime % change)
else :
nxtTime = currTime + time
# Add future cases
for nxt in paths[curr] :
heapq.heappush(toVisit, (nxtTime, nxt))
return dist2[-1]
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
paths = [[] for _ in range(n + 1)]
for u, v in edges :
paths[u].append(v)
paths[v].append(u)
dist1 = [0] + [inf] * n
dist2 = dist1.copy()
# schema: (time when reached, current node no.)
toVisit = deque([(0, 1)])
while toVisit :
currTime, curr = toVisit.popleft()
# If first case and second case already found
if dist1[curr] != inf and dist2[curr] != inf :
continue
# Repeat distance
if currTime == dist1[curr] :
continue
# If not found so insert
if dist1[curr] == inf :
dist1[curr] = currTime
else :
dist2[curr] = currTime
# If "red light," adjust time
if currTime % (2 * change) >= change :
nxtTime = currTime + time + change - (currTime % change)
else :
nxtTime = currTime + time
# Add future cases
for nxt in paths[curr] :
toVisit.append((nxtTime, nxt))
return dist2[-1]