Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3628. Find Minimum Time to Reach Last Room II

My accepted Python solution to LeetCode problem 3628, Find Minimum Time to Reach Last Room II, running in 2427ms.

  • Difficulty: Medium
  • Python
  • Runtime 2427ms
  • Memory 135.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 2427ms, memory 135.2MB, accepted 2025-12-31.

python
class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        import heapq
        n, m = len(moveTime), len(moveTime[0])
        # dist[r][c][parity] - parity 0 means next move costs 1, parity 1 means next move costs 2
        dist = [[[float('inf')] * 2 for _ in range(m)] for _ in range(n)]
        dist[0][0][0] = 0
        pq = [(0, 0, 0, 0)]  # (time, row, col, parity)
        
        while pq:
            t, r, c, p = heapq.heappop(pq)
            if r == n - 1 and c == m - 1:
                return t
            if t > dist[r][c][p]:
                continue
            move_cost = 1 if p == 0 else 2
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    new_time = max(t, moveTime[nr][nc]) + move_cost
                    new_parity = 1 - p
                    if new_time < dist[nr][nc][new_parity]:
                        dist[nr][nc][new_parity] = new_time
                        heapq.heappush(pq, (new_time, nr, nc, new_parity))
        
        return min(dist[n-1][m-1][0], dist[n-1][m-1][1])

Source