Software Engineer

2 minute read

Problem Statement

leetcode problem link

Intuition

The problem is to determine the minimum time required to reach the bottom-right cell of a 2D grid, given certain movement costs and conditions that alternate at each step. The idea is to use a shortest path algorithm (like Dijkstra’s) that adapts to the grid constraints and alternating movement costs.

Approach

We model this as a shortest-path problem on a grid, where each cell has a time cost constraint (moveTime[row][col]) that affects the next move. The movement alternates between fast and slow (1 unit vs. 2 units) depending on a boolean alternate flag, which flips every move. We use a min-heap (priority queue) to always expand the node with the least accumulated time.

  1. Initialize a distance matrix to store the minimum time to reach each cell.
  2. Use a min-heap starting from the top-left cell (0,0) with time 0 and alternate=True.
  3. For each cell, explore all 4 directions (up, down, left, right).
  4. If the current time is less than the time constraint moveTime[r][c], wait until that time.
  5. Update the time based on whether it is an alternate (1 unit) or not (2 units) step.
  6. If this new time is better than the recorded time in distance, update and push to the heap.

Complexity

  • Time complexity:
    \(O(R \cdot C \cdot \log(R \cdot C))\)
    where ( R ) is the number of rows and ( C ) is the number of columns. Each cell may be processed once in the priority queue.

  • Space complexity:
    \(O(R \cdot C)\)
    for the distance, visited, and heap storage.

Code

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        ROWS = len(moveTime)
        COLS = len(moveTime[0])
        distance = [[float('inf') for _ in range(COLS)] for _ in range(ROWS)]
        visited = [[False for _ in range(COLS)] for _ in range(ROWS)]
        min_heap = [[0, 0, 0, True]]
        distance[0][0] = 0
        while min_heap:
            time, row, col, alternate = heapq.heappop(min_heap)
            for x, y in [(0,1),(1,0),(-1,0),(0,-1)]:
                next_row = row + x
                next_col = col + y
                if 0 <= next_row < ROWS and 0 <= next_col < COLS and not visited[next_row][next_col]:
                    d = 0
                    if time < moveTime[next_row][next_col]:
                        d = moveTime[next_row][next_col] + (1 if alternate else 2)
                    else:
                        d = time + (1 if alternate else 2)
                    if d < distance[next_row][next_col]:
                        distance[next_row][next_col] = d
                        heapq.heappush(min_heap, [d, next_row, next_col, not alternate])
                    visited[next_row][next_col] = True

        return distance[-1][-1]

Editorial

Approach: Shortest Path + Dijkstra

class State:
    def __init__(self, x, y, dis):
        self.x = x
        self.y = y
        self.dis = dis

    def __lt__(self, other):
        return self.dis < other.dis


class Solution:
    def minTimeToReach(self, moveTime):
        n = len(moveTime)
        m = len(moveTime[0])
        inf = float("inf")
        d = [[inf] * m for _ in range(n)]
        v = [[0] * m for _ in range(n)]

        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        d[0][0] = 0
        q = []
        heapq.heappush(q, State(0, 0, 0))

        while q:
            s = heapq.heappop(q)
            if v[s.x][s.y]:
                continue
            if s.x == n - 1 and s.y == m - 1:
                break
            v[s.x][s.y] = 1
            for dx, dy in dirs:
                nx, ny = s.x + dx, s.y + dy
                if not (0 <= nx < n and 0 <= ny < m):
                    continue
                dist = max(d[s.x][s.y], moveTime[nx][ny]) + (s.x + s.y) % 2 + 1
                if d[nx][ny] > dist:
                    d[nx][ny] = dist
                    heapq.heappush(q, State(nx, ny, dist))

        return d[n - 1][m - 1]

You may also enjoy