Most grid problems tempt you to simulate. This one gives you a free choice of starting cell, which makes simulation look even more natural: try every cell and see if one survives. Then the constraints arrive, and you need a different idea.
So this post is written as an interview transcript. You get the vague version of the problem, ask questions, propose something slightly wrong, and get corrected. That process is what an interviewer actually grades.
The problem is Trace Path from GeeksforGeeks. It is rated Easy and tagged Matrix. The trap is the first shortcut almost everyone reaches for: counting how far the moves take you net and comparing that to the grid size. That checks where you end, but the question is about everywhere you went.
The one-line spoiler, for the skimmers and the language models: horizontal moves never change the row and vertical moves never change the column, so the grid splits into two independent 1D problems. On each axis, a valid start exists exactly when the path's span (farthest offset one way minus farthest offset the other way) is smaller than the axis length. The solution tracks this as one shrinking interval per axis in O(|s|) time, no matter how large the grid is.
Prefer to watch the walkthrough? It covers the same ground as this transcript:
Now the transcript.
Minute 0: The problem, stated loosely
Interviewer: There's a grid,
nrows bymcolumns. I give you a string of moves: L, R, U, D. You pick any starting cell and follow every move in order. Tell me whether some starting cell keeps you inside the grid the whole time.
The interviewer gave no limits, no indexing, and no direction convention. That is on purpose. The first thing being graded is whether you clarify before you start coding.
You: A few questions first.
- How big can
n,m, and the string get?- Does "inside the whole time" mean after every move, or only at the end?
- Which way is U? Does row index go up or down?
- Do I return the cell, or just true/false?
Interviewer: All three are up to 10^4. Every move must stay inside, not just the last one. Just a boolean. And on direction, the statement says
Dtakes you from(i, j)to(i - 1, j)andUtakes you to(i + 1, j).You: So D is "up" and U is "down" if row 1 is on top. That's backwards from usual, but I don't think it matters. If I flip the grid top to bottom, every valid start becomes another valid start. Only the fact that U and D are opposites matters.
Why this beat scores: question 2 is the real hook, and the U/D question shows you can tell which details matter and which don't. (I ran the solution on 20,000 random inputs with U and D swapped. The answer changed 0 times.)
Minute 3: Draw the smallest case first
You: Take the second example:
n = 2, m = 3, s = "LLRU". Start at row 1, column 3.
col 1 col 2 col 3
row 1 [ 3 ] [ 2,4 ] [ S ] S = start
row 2 [ ] [ 5 ] [ ] L, L, R, then U
Column offsets from start: 0, -1, -2, -1, -1
Row offsets from start: 0, 0, 0, 0, +1
You: The columns go two to the left of the start and never to the right, so they cover 3 columns. That fits in
m = 3exactly. The rows cover 2, which fits inn = 2. So the answer is true.
Notice what the drawing already shows: the columns and rows were checked separately, and neither check looked at the other axis.
Why this beat scores: you found the structure (two independent axes, a "covered width" per axis) by drawing, not by recalling a pattern.
Minute 6: The tempting shortcut
You: So maybe I just count. If
|#R − #L| < mand|#U − #D| < n, then it fits.Interviewer: Try
s = "RL"on a 1 × 1 grid.You: Net horizontal displacement is zero, so my check says true. But the very first move, R, takes me off a one-column grid. So the answer is false and my check is wrong.
You: Right. Net displacement only tells me where I end. What I need is the farthest right minus the farthest left at any point along the way. That's the span of the path.
"RRLL"on a 1 × 2 grid has the same problem: I end where I started, but at one point I'm two columns to the right, so I need 3 columns.
Why this beat scores: you answered the pushback with a concrete counterexample, and that counterexample changed what you measure.
Minute 9: Brute force, out loud
You: The baseline is to try every start cell and simulate the whole string from it. That's
n · m · |s|, which is10^12at the limits. Way too slow.You: But it also wastes work. Every start runs the same moves. The starts only differ in where they begin, so I should handle all of them at once.
Minute 11: One interval per axis
You: On a single axis of length
m, think of a walker standing in every cell. On each move, they all shift by one. The walker at the edge they move toward falls off, and everyone else stays in. The survivors are always one contiguous block, so I only need its two ends,minandmax. If the block ever becomes empty, no start works.Interviewer: And the rows?
You: The same function with
nand the other two letters. A move on the other axis leaves the interval alone. A start works exactly when its column survives the column check and its row survives the row check.
Minute 14: Writing it
class Solution {
public boolean isPossible(int n, int m, String s) {
// code here
return
check(s, 1, m, 'L', 'R')
&& check(s, 1, n, 'U', 'D');
}
boolean check(
String s, int l, int r, char sub, char add
) {
int min, max;
min = l; max = r;
for (char ch : s.toCharArray()) {
if (ch == add) {
max -= 1;
min = Math.max(l, min-1);
} else if (ch == sub) {
min += 1;
max = Math.min(r, max+1);
}
if (min > max) return false;
}
return min <= max;
}
}
You: One edge loses a walker (
max -= 1ormin += 1). The other edge moves by one but gets clamped back onto the grid, because nobody can be standing outside it.
Minute 17: The line the interviewer asks about
Interviewer: Why do you need the
Math.maxandMath.min? Couldn't the interval just slide?You: If it slides without clamping, its width only shrinks when a walker falls off one side, and the far edge drifts out past the grid. Then the interval never empties when it should. I checked both versions against a brute force:
without Math.max(l, min-1): n=1, m=1, s="R" -> true (correct: false)
without Math.min(r, max+1): n=1, m=3, s="RRLLLL" -> true (correct: false)
You: Across 20,000 random small grids, removing either clamp gives a wrong answer on about a quarter of them. The clamp is what makes this a span check instead of a net-displacement check.
Interviewer: Your
Rmove decrementsmax. Isn't that backwards? Moving right should push the walkers towardm.You: It's the mirror image. The code tracks positions as if measured from the opposite wall, so a step toward
rlooks like a step towardl. A path fits exactly when its mirror image fits. That's the same reason the U/D labels don't matter. The earlyreturn falseis just a shortcut, because an empty interval can never refill.
Why this beat scores: you can say which lines carry the logic, and you have evidence for it, not only an opinion.
Minute 20: Trace it before you claim it works
These intervals come straight from instrumenting the code on n = 2, m = 3, s = "LLRU":
columns: check(s, 1, 3, 'L', 'R')
start [min=1, max=3]
'L' [min=2, max=3]
'L' [min=3, max=3]
'R' [min=2, max=2]
'U' [min=2, max=2] <- vertical move, columns untouched
rows: check(s, 1, 2, 'U', 'D')
start [min=1, max=2]
'L' [min=1, max=2]
'L' [min=1, max=2]
'R' [min=1, max=2]
'U' [min=2, max=2]
both non-empty -> true
And the first example, n = 1, m = 1, s = "R":
columns: check(s, 1, 1, 'L', 'R')
start [min=1, max=1]
'R' [min=1, max=0] <- empty, return false
Minute 22: Can you do better?
Interviewer:
O(|s|). Can you beat it?You: No. The last character alone can push the path off the grid, so any correct algorithm has to read all of
s.O(|s|)is the floor, and the grid size never appears in the cost.Interviewer: Is there a simpler way to say the same thing?
You: Yes, as the span check directly. Track the running offset on each axis and its lowest and highest values. A start exists exactly when each span fits:
static boolean span(int n, int m, String s) {
int x = 0, y = 0, minX = 0, maxX = 0, minY = 0, maxY = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == 'L') x--; else if (ch == 'R') x++;
else if (ch == 'D') y--; else y++;
minX = Math.min(minX, x); maxX = Math.max(maxX, x);
minY = Math.min(minY, y); maxY = Math.max(maxY, y);
}
return maxX - minX < m && maxY - minY < n;
}
You: I compared this against both a brute force and the interval version over the same 20,000 random inputs, and it matched every time. It's one pass instead of two, and it uses
O(1)extra space becausecharAtavoids thetoCharArray()copy. The interval version is easier to reason about step by step. The span version makes the reason clear.
Minute 25: Edge cases
-
A 1-wide axis. With
m = 1, anyLorRfails right away. Withn = 5, m = 1, s = "UU", the answer is true because you can walk along a single column. A check that mixed the axes would get this wrong. - Moves on only one axis. The other axis's interval never changes and stays the whole range.
-
Returning to the start.
"RL"on 1 × 1 and"RRLL"on 1 × 2 are both false. Ending where you began proves nothing. -
When this solution stops being the right shape. If you're asked the same question for many grid sizes with one string, don't re-run the interval check each time. Compute the two spans once, and then each query is an
O(1)comparison. If you're asked about every suffix of the string (LeetCode 2120), you need a different approach.
What was actually being graded
| Beat | What it signals |
|---|---|
| Asked "every step, or just the end?" | You found the hook before writing code |
| Dismissed the U/D labeling with a symmetry argument | You can tell which details matter |
Broke the net-displacement idea with "RL"
|
You test your ideas against small counterexamples |
| Split 2D into two 1D problems | You look for independent structure |
| Explained the clamp with a failing input | You know which line does the real work |
| Gave a lower bound for "can you do better?" | You can justify stopping |
Red flags, taken from real attempts
Checking only the final position. |#R − #L| < m passes "RL" on a 1 × 1 grid, but the answer is false.
Dropping a clamp. Without Math.max(l, min-1), n = 1, m = 1, s = "R" returns true. Without Math.min(r, max+1), n = 1, m = 3, s = "RRLLLL" returns true.
Simulating every start. It's correct, but at 10^12 steps it times out.
Mixing the axes. If a vertical move changes the column interval, n = 5, m = 1, s = "UU" returns false.
"Fixing" the U/D labels and getting confused. It changes nothing. Treat U and D as an opposite pair.
FAQ
Why is checking net displacement wrong for Trace Path?
Net displacement only tells you where the path ends, but you must stay inside the grid after every move. "RL" on a 1 × 1 grid ends at the start but leaves the grid on the first step. What has to fit is the span: the farthest offset in one direction minus the farthest in the other.
Why can rows and columns be checked separately?
L and R never change the row, and U and D never change the column. So a start cell is valid exactly when its column is valid for the horizontal moves and its row is valid for the vertical ones. The two checks never interact.
Does it matter that D moves up and U moves down in the statement?
No. Mirroring the grid top to bottom swaps the meaning of U and D and turns every valid start into another valid start. Swapping U and D in 20,000 random test strings never changed the answer.
What is the time and space complexity of Trace Path?
The interval solution is O(|s|) time: one pass per axis, constant work per character, and independent of n and m. It uses O(|s|) space only because toCharArray() copies the string. The span version with charAt is O(1) extra space. (This is my analysis of the code. GFG does not publish expected complexities for this problem.)
Why doesn't brute force over all start cells work?
It costs n · m · |s|, which is 10^12 at the given limits. Every start runs the same moves, so tracking all of them as one interval per axis gives the same answer in O(|s|).
Is there a faster solution than O(|s|)?
No. The last move alone can push the path out of the grid, so every correct algorithm has to read the whole string.
Takeaways
- Ask whether the constraint applies at every step or only at the end. That one question separates the right check from the shortcut that fails.
- When everyone runs the same moves, track a set, not individuals. A "pick any start" problem usually means tracking the range of starts that still work.
- Look for axes that don't interact. A 2D question with separable moves is two 1D questions.
-
Break your own shortcut before the interviewer does. A two-character counterexample like
"RL"is the fastest way to show you understand why the real answer works.
Full Java solution and a detailed write-up: github.com/KodeLoad/DailyKodePractice
Video walkthrough:
Did you reach for net displacement first too? I'd like to hear what made you catch it, or what didn't, in the comments.
Top comments (0)