Trace Path

Problem Statement

Given a rectangular grid of size n × m and a string s containing movement commands, Geek can start from any cell in the grid.

The string contains only:

• L → Move one cell left
• R → Move one cell right
• D → Move one cell up
• U → Move one cell down

We need to determine whether there exists at least one starting cell such that Geek can follow the complete path without leaving the grid.

Example 1

n = 1
m = 1
s = "R"

There is only one cell.

(0,0) → R → (0,1)

The second position is outside the grid.

Therefore:

Output: false

Example 2

n = 2
m = 3
s = "LLRU"

One possible path is:

(0,2)
   ↓ L
(0,1)
   ↓ L
(0,0)
   ↓ R
(0,1)
   ↓ U
(1,1)

All positions are inside the 2 × 3 grid.

Therefore:

Output: true

Main Idea

A straightforward approach would be to try every cell as the starting point.

But that is unnecessary.

Instead, we can look at the path relative to the starting cell.

Suppose we start at:

(0, 0)

and process the commands.

We don't care about the actual starting position yet. We only need to know:

• How far up/down can the path go?
• How far left/right can the path go?

For this, we maintain:

minRow
maxRow
minCol
maxCol

These values describe the bounding rectangle of the complete path.

Understanding the Coordinates

We use:

row = 0
col = 0

as the relative starting position.

According to the problem:

L → col--
R → col++

D → row--
U → row++

For every movement, we update the current position.

Then we update the minimum and maximum row and column.

Example

Consider:

s = "LLRU"

Start with:

row = 0
col = 0

Command L

row = 0
col = -1

Command L

row = 0
col = -2

Command R

row = 0
col = -1

Command U

row = 1
col = -1

Therefore:

minRow = 0
maxRow = 1

minCol = -2
maxCol = 0

The required number of rows is:

maxRow - minRow + 1
= 1 - 0 + 1
= 2

The required number of columns is:

maxCol - minCol + 1
= 0 - (-2) + 1
= 3

So the path requires a:

2 × 3

grid.

Since the given grid is also:

2 × 3

the path fits.

Hence the answer is:

true

Why Do We Add +1?

This is an important point.

Suppose the path visits:

columns: -2, -1, 0

The difference between maximum and minimum is:

0 - (-2) = 2

But there are actually 3 cells:

-2 → -1 → 0

Therefore:

requiredCols = maxCol - minCol + 1

Similarly:

requiredRows = maxRow - minRow + 1

Algorithm

Follow these steps:

1. Start at relative position (0, 0).

2. Initialize:

   CodeCopy

   minRow = 0
   maxRow = 0
   minCol = 0
   maxCol = 0

3. Traverse every character in s.
4. Update row and col according to the command.
5. Update the minimum and maximum row/column.

6. Calculate:

   CodeCopy

   requiredRows = maxRow - minRow + 1
   requiredCols = maxCol - minCol + 1

7. If:

   CodeCopy

   requiredRows <= n
   AND
   requiredCols <= m

   return true.

8. Otherwise, return false.

Java Code

class Solution {
    public boolean isPossible(int n, int m, String s) {

        int row = 0;
        int col = 0;

        int minRow = 0;
        int maxRow = 0;
        int minCol = 0;
        int maxCol = 0;

        for (char ch : s.toCharArray()) {

            if (ch == 'L') {
                col--;
            } 
            else if (ch == 'R') {
                col++;
            } 
            else if (ch == 'D') {
                row--;
            } 
            else if (ch == 'U') {
                row++;
            }

            minRow = Math.min(minRow, row);
            maxRow = Math.max(maxRow, row);

            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);
        }

        int requiredRows = maxRow - minRow + 1;
        int requiredCols = maxCol - minCol + 1;

        return requiredRows <= n && requiredCols <= m;
    }
}

Code Explanation

1. Current Position

int row = 0;
int col = 0;

We assume that the starting cell is (0,0).

This is only a relative coordinate system. We will later shift the entire path to an appropriate starting cell.

2. Minimum and Maximum Coordinates

int minRow = 0;
int maxRow = 0;
int minCol = 0;
int maxCol = 0;

These variables store the extreme positions reached by the path.

For example:

minRow = -2
maxRow = 3

means the path covers 6 rows:

-2, -1, 0, 1, 2, 3

3. Process Every Command

for (char ch : s.toCharArray()) {

We process the string one character at a time.

4. Handle Movement

For left:

if (ch == 'L') {
    col--;
}

For right:

else if (ch == 'R') {
    col++;
}

For up:

else if (ch == 'D') {
    row--;
}

For down:

else if (ch == 'U') {
    row++;
}

The important thing is to follow the direction definitions given in the problem.

5. Update Boundaries

After every movement:

minRow = Math.min(minRow, row);
maxRow = Math.max(maxRow, row);

minCol = Math.min(minCol, col);
maxCol = Math.max(maxCol, col);

This records the complete area occupied by the path.

Why Don't We Need to Try Every Starting Cell?

Suppose the relative path is:

(-2,0)
(-1,0)
(0,0)
(1,0)

We can shift the entire path to the right/down.

For example:

(0,0)
(1,0)
(2,0)
(3,0)

The shape of the path doesn't change.

Therefore, instead of checking every starting cell, we only need to know the size of the bounding rectangle.

This reduces the problem from potentially checking many cells to simply scanning the string once.

Example Dry Run

Consider:

n = 3
m = 3
s = "RRUULL"

Initial:

row = 0
col = 0

Process commands:

Therefore:

minRow = 0
maxRow = 2

minCol = 0
maxCol = 2

Required size:

Rows = 2 - 0 + 1 = 3
Cols = 2 - 0 + 1 = 3

Given grid:

3 × 3

So:

3 <= 3  → true
3 <= 3  → true

Answer:

true

Another Example

Consider:

n = 2
m = 2
s = "RR"

Path:

(0,0)
(0,1)
(0,2)

The required width is:

2 - 0 + 1 = 3

But the grid has only 2 columns.

3 > 2

Therefore:

false

No matter where we start, moving right twice requires three columns.

Complexity Analysis

Let:

k = s.length()

We scan the string exactly once.

Time Complexity

O(k)

Auxiliary Space

We only use a fixed number of integer variables.

O(1)

This satisfies the expected complexity.

Important Insight

The most important concept in this problem is:

Do not simulate the path from every possible starting cell. Find the bounding rectangle of the path instead.

The path can be shifted to any location in the grid.

Therefore, only these two things matter:

Required Height
Required Width

If:

requiredRows <= n

and

requiredCols <= m

then a valid starting cell exists.

Common Mistake

A common approach is:

for every cell:
    simulate the entire string

This can take approximately:

O(n × m × |s|)

which is unnecessary.

The optimized approach is:

simulate the path once
        ↓
find min/max row and column
        ↓
calculate required dimensions
        ↓
compare with grid dimensions

So we get:

O(|s|)

Final Takeaway

This problem teaches an important technique used in grid and movement problems:

Instead of checking every starting position:

1. Treat the starting point as (0,0).
2. Follow the movements.
3. Find the minimum and maximum row/column.
4. Calculate the bounding rectangle.
5. Check whether that rectangle fits inside the given grid.

The final condition is simply:

return requiredRows <= n && requiredCols <= m;

This gives an efficient:

Time:  O(|s|)
Space: O(1)

solution.