You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].
You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.
Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.
Example 1:
Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]] Output: 7 Explanation: One of the paths that we can take is the following: - at t = 0, we are on the cell (0,0). - at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1. - at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2. - at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3. - at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4. - at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5. - at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6. - at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7. The final time is 7. It can be shown that it is the minimum time possible.
Example 2:
Input: grid = [[0,2,4],[3,2,1],[1,0,4]] Output: -1 Explanation: There is no path from the top left to the bottom-right cell.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1050 <= grid[i][j] <= 105grid[0][0] == 0
This approach uses a priority queue to implement a modified version of Dijkstra's algorithm. The challenge here includes managing both the time constraints specified by the grid and the movement cost. The goal is to find the shortest path in terms of time while making sure each cell is entered at a valid time.
We use a priority queue to determine which cell to visit next based on the minimum time it takes to safely visit it. This is similar to choosing the shortest weighted edge in Dijkstra's algorithm, but our 'weight' here is the time passed.
The Python solution uses a heap priority queue to manage cells to visit by their prospective visit time. We maintain a set of visited cells to prevent re-evaluation. For each cell, we consider its neighboring cells and calculate any necessary wait time based on the grid's constraints.
Java
C++
JavaScript
Time Complexity: O(m*n*log(m*n)) due to heap operations for each cell.
Space Complexity: O(m*n) to store the visited set.
This approach uses a breadth-first search (BFS) where we evaluate the grid level by level. Instead of using a priority queue, the BFS explores nodes in increasing order of time levels, trying to meet grid constraints at each level. It tracks the earliest time a cell can be safely visited.
The Python solution applies BFS using a deque structure to simulate levels of operation, maintaining an auxiliary matrix to record the earliest times a cell can be visited, ensuring grid constraints are respected.
Java
C++
JavaScript
Time Complexity: O(m*n)
Space Complexity: O(m*n)
| Approach | Complexity |
|---|---|
| Priority Queue with Dijkstra-Like Approach | Time Complexity: O(m*n*log(m*n)) due to heap operations for each cell. |
| Breadth-First Search with Level Traversal | Time Complexity: O(m*n) |
Minimum Time to Visit a Cell In a Grid - Leetcode 2577 - Python • NeetCodeIO • 10,784 views views
Watch 9 more video solutions →Practice Minimum Time to Visit a Cell In a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor