[Leetcode] 3341. Find Minimum Time to Reach Last Room I

https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/description/?envType=daily-question&envId=2025-05-07

initial

a typical dijkstra question but i just tried doing via dfs and got an issue

btw to explore this path further, the condition is to

next_time=max(moveTime[next_x][next_y],cur_cost)+1

and to optimise the dijkstra search, we dont explore this particular path if there is a previously explored path that has a lower cost than cur_cost.

                if cur_cost>=visited[cur_x][cur_y]:
                    continue

initial dfs way that caused tle:

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        ans=[]
        moves=[[1,0],[-1,0],[0,1],[0,-1]]
        visited=[[False for _ in range(len(moveTime[0]))] for _ in range(len(moveTime))]

        def dfs(cur_x,cur_y,cur_cost):
            nonlocal ans
            visited[cur_x][cur_y]=True
            if cur_x==len(moveTime)-1 and cur_y==len(moveTime[0])-1:
                ans.append(cur_cost)
                return
            for move in moves:
                next_x,next_y=move[0]+cur_x,move[1]+cur_y
                if 0<=next_x<len(moveTime) and 0<=next_y<len(moveTime[0]):
                    if not visited[next_x][next_y]:
                        next_time=moveTime[next_x][next_y]
                        if cur_cost<next_time:
                            dfs(next_x,next_y,next_time+1)
                            visited[next_x][next_y]=False
                        else:
                            dfs(next_x,next_y,cur_cost+1)
                            visited[next_x][next_y]=False
            return cur_cost
        dfs(0,0,0)
        print(ans)
        return min(ans)

            

sol

dijkstra

import heapq
class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        heap=[]
        ans=[]
        heapq.heapify(heap)
        moves=[[1,0],[-1,0],[0,1],[0,-1]]
        visited=[[int(10e9) for _ in range(len(moveTime[0]))] for _ in range(len(moveTime))]

        def dijkstra():
            nonlocal heap,ans
            while heap:
                cur_cost,cur_x,cur_y=heapq.heappop(heap)
                if cur_cost>=visited[cur_x][cur_y]:
                    continue
                if cur_x==len(moveTime)-1 and cur_y==len(moveTime[0])-1:
                    ans.append(cur_cost)
                    return
                visited[cur_x][cur_y]=cur_cost
                for move in moves:
                    next_x,next_y=move[0]+cur_x,move[1]+cur_y
                    if 0<=next_x<len(moveTime) and 0<=next_y<len(moveTime[0]) and visited[next_x][next_y]==int(10e9):
                        next_time=max(moveTime[next_x][next_y],cur_cost)+1
                        heapq.heappush(heap,(next_time,next_x,next_y))
        heapq.heappush(heap,(0,0,0))
        dijkstra()
        print(ans)
        return min(ans)

            

complexity

heapq heappush and heappop is log(v), where v is number of vertices (points).

Time ComplexityInitialization:visited array initialization: O(n m), where n is the number of rows and m is the number of columns in moveTime.Heap initialization: O(1)Dijkstra's Algorithm:The while loop runs at most n m times because each cell is visited at most once.Inside the loop:heapq.heappop(): O(log(V)), where V is the number of vertices in the heap. In the worst case, V can be n m. So, O(log(n m)).Visiting neighbors: O(1) since there are at most 4 neighbors.heapq.heappush(): O(log(V)) = O(log(n m)).Overall time complexity: O(n m log(n m)).Total Time Complexity: O(n m) + O(n m log(n m)) which simplifies to O(n m log(n * m)).

Space Complexityheap: In the worst case, the heap can contain all the cells in the grid, so its space complexity is O(n m).visited: O(n m) to store the minimum times to reach each cell.Other variables: O(1) (constant).Total Space Complexity: O(n m) + O(n m) + O(1) which simplifies to O(n * m).