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.

Description Hints 2 Solution Video 14:13

4084. Last Visited Cell in a Directional Grid

Medium66.9% acceptance

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 <= 10⁵
1 <= n == grid[i].length <= 10⁵
m * n <= 10⁵
grid[i][j] is one of 'L', 'R', 'U', or 'D'.

Hints open one at a time

Hint 1

Follow the directions while recording visited cells. You can use a separate visited array or mark cells in place after reading their directions.

Hint 2

Calculate the next position before moving. If it is outside the grid or already visited, return the current position.

14:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[["R","D"],["U","L"]]

Input

[["R","R","R"]]

Your code is saved on this device.Solution