Last Visited Cell in a Directional Grid solution and explanation
5 more videos on this problem
Last Visited Cell in a Directional Grid | LeetCode 4084 |Weekly Contest 524 | Dry RunVijay Algorithms · 14:13 · 48 views
LeetCode Weekly Contest 524 | 4083 & 4084 Explained in Java | First 2 ProblemsProof2Code · 12:12 · 36 views
Last Visited Cell in a Directional Grid | Leetcode Problem number 4084 | Weekly contest 524.Prince Gupta Study · 18:54 · 30 views
LeetCode 4084: Last Visited Cell in a Directional Grid | Java Solution | MediumCakot Coding · 13:09 · 26 views
LeetCode 4084 Last Visited Cell in a Directional Grid — why the walk must stopPrateek Goel · 13:46 · 16 views
Last Visited Cell in a Directional GridOwen Wu · 4:00 · 5 views
The problem
You are given an m x n matrix grid where each cell contains one of the following characters:
'L': move one cell left.'R': move one cell right.'U': move one cell up.'D': move one cell down.
You start at cell (0, 0), which is considered visited. At each step, move to the cell indicated by the character in your current cell.
The process ends if the indicated move would either leave the grid or enter a cell that has already been visited. In either case, the move is not made.
Return an integer array [r, c] representing the row and column indices of the last visited cell. The indices are 0-based.
Example 1:
Input: grid = [["R","D"],["U","L"]]
Output: [1,0]
Explanation:
- Start at cell
(0, 0), which contains'R', so move right to(0, 1). - At cell
(0, 1), the character is'D', so move down to(1, 1). - At cell
(1, 1), the character is'L', so move left to(1, 0). - At cell
(1, 0), the character is'U', which indicates moving to(0, 0). However,(0, 0)has already been visited, so this move is not made. - Therefore, the process ends at the last visited cell
(1, 0), so the answer is[1, 0].
Example 2:
Input: grid = [["R","R","R"]]
Output: [0,2]
Explanation:
- Start at cell
(0, 0), which contains'R', so move right to(0, 1). - At cell
(0, 1), the character is'R', so move right to(0, 2). - At cell
(0, 2), the character is'R', which indicates moving to(0, 3). However,(0, 3)is outside the grid, so this move is not made. - Therefore, the process ends at the last visited cell
(0, 2), so the answer is[0, 2].
Constraints:
1 <= m == grid.length <= 1051 <= n == grid[i].length <= 105m * n <= 105grid[i][j]is one of'L','R','U', or'D'.
Approach overview
Problem Overview: You start at the top-left cell of a grid and move according to the value stored in each cell. The task is to follow these moves until you cannot continue, then return the last cell you visited. The grid values define how far each jump goes, so the path is fully determined once you know the current cell.
Approach 1: Brute Force Simulation (O(m * n * max(m, n)) time, O(1) extra space)
Start at (0, 0) and mark it visited. From the current cell, scan every legal target in the allowed directions, up to the jump length stored in the cell. Pick the next unvisited cell in the rule's order, move there, and repeat. Each step scans up to a full row or column, so the total work grows quickly on large grids. Use this to confirm you understand the movement rules before optimizing.
Approach 2: Simulation with Visited Tracking Per Row and Column (O(m * n) time, O(m * n) space)
Keep a sorted structure for each row and each column that records which indices are already visited or can be skipped. When you jump, you query these structures for the next candidate index instead of scanning every cell. A visited boolean grid alone is not enough because the scan still touches blocked cells repeatedly. Pairing the grid with a next-pointer per row and column lets you skip over visited ranges in amortized constant time per step. This is the approach most people reach after the brute force, and it is the one to implement in an interview.
Approach 3: Memoized Path Computation (O(m * n) time, O(m * n) space)
Because each cell determines its successor, the movement forms a chain over the grid. Compute the answer for each cell once and store it in a memo table. When a later path hits a cell whose result you already know, return it directly. This avoids recomputing identical suffixes of the path. The memo table is the same size as the grid, so you trade memory for guaranteed linear work over the cells.
Recommended for interviews: Interviewers expect you to start with the direct simulation to show you understand the movement rules. The brute force proves correctness, but the optimized version with row and column tracking or memoization shows you can handle the grid size constraints. Explain the bottleneck of the scan first, then fix it with a structure that skips visited cells.
Related topics: simulation, matrix, dynamic programming.
Solution
Thinking
The grid has at most
10^5cells. Following the arrows without remembering visited cells never stops once the path enters a cycle.Movement ends in only two cases: the next step would leave the grid, or it would enter a cell that was already visited. In both cases that step is not taken, and the answer is the previous valid coordinate.
Each cell is entered at most once. Mark visits in a two-dimensional boolean array, start at
(0,0), update the row and column from the current character, and return the saved coordinate when the next step is illegal.
Simulate from (0,0). Use a boolean array vis to mark cells that have already been visited. At each step, save the current coordinate (r,c), then move according to grid[r][c]: L and R change the column, while U and D change the row. If the new coordinate is outside the grid or its cell has already been visited, do not take that step and return the saved coordinate. Each cell is visited at most once.
The time complexity is O(mn) and the space complexity is O(mn), where m and n are the number of rows and columns.
class Solution:
def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
m, n = len(grid), len(grid[0])
r = c = 0
vis = [[False] * n for _ in range(m)]
while 1:
cur = [r, c]
vis[r][c] = True
match grid[r][c]:
case "L":
c -= 1
case "R":
c += 1
case "U":
r -= 1
case "D":
r += 1
if 0 <= r < m and 0 <= c < n and not vis[r][c]:
continue
return curclass Solution {
public int[] lastVisitedCell(char[][] grid) {
int m = grid.length, n = grid[0].length;
int r = 0, c = 0;
boolean[][] vis = new boolean[m][n];
while (true) {
int[] cur = {r, c};
vis[r][c] = true;
switch (grid[r][c]) {
case 'L' -> c--;
case 'R' -> c++;
case 'U' -> r--;
case 'D' -> r++;
}
if (r >= 0 && r < m && c >= 0 && c < n && !vis[r][c]) {
continue;
}
return cur;
}
}
}class Solution {
public:
vector<int> lastVisitedCell(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int r = 0, c = 0;
vector<vector<bool>> vis(m, vector<bool>(n));
while (true) {
vector<int> cur = {r, c};
vis[r][c] = true;
switch (grid[r][c]) {
case 'L': c--; break;
case 'R': c++; break;
case 'U': r--; break;
case 'D': r++; break;
}
if (r >= 0 && r < m && c >= 0 && c < n && !vis[r][c]) {
continue;
}
return cur;
}
}
};function lastVisitedCell(grid: string[][]): number[] {
const m = grid.length,
n = grid[0].length;
let r = 0,
c = 0;
const vis = Array.from({ length: m }, () => Array(n).fill(false));
while (true) {
const cur = [r, c];
vis[r][c] = true;
switch (grid[r][c]) {
case 'L':
c--;
break;
case 'R':
c++;
break;
case 'U':
r--;
break;
case 'D':
r++;
break;
}
if (r >= 0 && r < m && c >= 0 && c < n && !vis[r][c]) {
continue;
}
return cur;
}
}func lastVisitedCell(grid [][]byte) []int {
m, n := len(grid), len(grid[0])
r, c := 0, 0
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
for {
cur := []int{r, c}
vis[r][c] = true
switch grid[r][c] {
case 'L':
c--
case 'R':
c++
case 'U':
r--
case 'D':
r++
}
if r >= 0 && r < m && c >= 0 && c < n && !vis[r][c] {
continue
}
return cur
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(m * n * max(m, n)) | O(1) | Small grids or verifying rules |
| Simulation with Row and Column Tracking | O(m * n) | O(m * n) | General case and interviews |
| Memoized Path Computation | O(m * n) | O(m * n) | When many paths share suffixes |
Frequently asked questions
Is Last Visited Cell in a Directional Grid easy or hard?
It is a Medium problem with an acceptance rate of about 66.9 percent. The difficulty comes from carefully following the movement rules and choosing the right skip structure, not from advanced algorithms. Practicing grid simulation problems builds the skills it tests.
How to solve Last Visited Cell in a Directional Grid in O(n)?
Treat the grid as a chain where each cell points to its successor, then process cells with memoization so each one is computed once. Track visited cells with per-row and per-column structures so every skip is amortized constant time. Together these keep total work proportional to the number of cells.
Last Visited Cell in a Directional Grid Python and Java solution?
Both languages use the same simulation logic: track the current cell, compute the next jump, and skip visited positions with row and column structures. In Python, use lists and bisect-style lookups; in Java, use TreeSet or arrays of pointers. The complexity and approach are identical across languages.
What is the best approach for Last Visited Cell in a Directional Grid?
The best approach is simulation with per-row and per-column tracking, which runs in O(m * n) time. It skips visited cells efficiently instead of rescanning the grid on every jump. Memoized path computation is an equally linear alternative when paths overlap.
What data structure is used in Last Visited Cell in a Directional Grid?
The core structure is a 2D grid for the cell values and a visited marker. The optimized version adds sorted or pointer-based structures per row and column to skip visited indices. A memo table of size m * n is used in the memoized variant.
What is the time complexity of Last Visited Cell in a Directional Grid?
The optimal solution runs in O(m * n) time, where m and n are the grid dimensions. The brute force scan costs O(m * n * max(m, n)) because each step can scan an entire row or column. The space cost of the optimized version is O(m * n) for tracking structures.
Is Last Visited Cell in a Directional Grid asked at Google, Amazon, or Meta?
This problem is a Medium-level simulation question that appears in general practice sets. Company-specific frequency is not confirmed here, so check recent interview reports on your target company's question list. Focus on the simulation logic, since that pattern transfers to many grid problems.