Rat in a Maze

Given a square binary grid mat of size n x n, a rat starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (n - 1, n - 1).

A cell with value 1 is open — the rat may stand on it.
A cell with value 0 is blocked — the rat may never enter it.

The rat moves one step at a time in the four directions up (U), down (D), left (L), and right (R). It may travel only through open cells, and may not visit the same cell twice within a single path.

Return all valid paths from the source to the destination. Each path is the string of moves the rat takes to get there. If no path exists, return an empty list.

Hints

· Stuck? Reveal one nudge at a time.

You're not looking for one path — you're looking for every path. What technique explores all the choices and cleanly undoes the ones that fail?

As you walk a trail, mark each cell so you don't loop back onto yourself; the instant you back out of a cell, unmark it so a future path can still use it.

Try the four directions in the order D, L, R, U. Because that's alphabetical, the paths you finish come out already sorted — no final sort needed.

Common doubts

It means no simple path of open cells connects the top-left corner to the bottom-right — for example when the destination cell is blocked. In that case return an empty list.

Each path must be simple. Revisiting would create loops and infinitely many 'paths', so we mark cells on the current trail and skip any that are already marked.

Yes. A cell blocked in one path may be essential in another. Marking on enter and unmarking on leave keeps each path independent while sharing a single grid.

Interview follow-ups

· What an interviewer asks next.

Run a plain DFS or BFS for reachability and return as soon as the destination is reached — that turns it into an O(n^2) search instead of enumerating every route.

Extend the direction list with the new offsets and move characters. The mark/unmark backbone stays identical; only the neighbour-generation step changes.

Switch from backtracking to BFS, which explores by distance and finds a shortest route first — backtracking enumerates all paths and isn't built for shortest-only queries.

Fun facts

The 'mark on enter, unmark on leave' rhythm is the same trick that powers N-Queens, Sudoku solvers, and word-search grids — learn it once and reuse it everywhere.
Counting (not even listing) the self-avoiding paths from corner to corner of a grid is a famously hard problem with no known simple formula — the counts explode so fast they fill their own combinatorics tables.

Asked at

AmazonMicrosoftGoogleAdobeFlipkart

Frequently Sometimes Occasionally

Example 1

Input: mat = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
Output: ["DDRDRR", "DRDDRR"]
Two trails reach the bottom-right corner: down-down-right-down-right-right and down-right-down-down-right-right.

Example 2

Input: mat = [[1,0],[1,0]]
Output: []
The destination cell (1,1) is blocked, so no path can reach it.

Constraints

- 2 <= n <= 5 - mat[i][j] is either 0 or 1 - mat is a square grid of size n x n

Rat in a Maze is the classic first taste of backtracking: make a move, and if it leads nowhere, quietly undo it and try the next. Master the mark-and-unmark rhythm here and every grid and backtracking problem afterward starts to feel familiar.

Prerequisites

Before you start

· Concepts used directly in the solution.

Grid traversal. Moving between cells using (row, col) offsets for up, down, left, and right.

Recursion and the call stack. Each cell you stand on is one stack frame; returning from it takes a step back.

Backtracking. Make a choice, recurse, then undo the choice so the next branch starts clean.

Lexicographic order. Why trying directions in D, L, R, U order makes the answer come out pre-sorted.

Understand the problem

In plain English: from cell (0, 0), walk only on open cells (value 1), never step on a cell already on your current trail, and record the moves — U, D, L, R — of every route that reaches (n-1, n-1).

Formally: given an n x n grid mat of 0s and 1s, return every string over {U, D, L, R} describing a simple path from (0, 0) to (n-1, n-1) that stays on cells equal to 1.

Worked example — n = 4

grid          one valid trail: D D R D R R
1 0 0 0       (0,0) -> (1,0) -> (2,0) -> (2,1) -> (3,1) -> (3,2) -> (3,3)
1 1 0 1
1 1 0 0       start: move Down twice, Right, Down, Right, Right
0 1 1 1       reach: bottom-right corner  OK

Both DDRDRR and DRDDRR reach the corner, so the answer is [DDRDRR, DRDDRR].

Clarifying questions

Naming the input guarantees before you code shows the interviewer you think in edge cases, not just the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the grid always square, and can the start or destination cell be blocked?”

If either corner is blocked the answer is immediately empty — a one-line guard at the top.

Path rules

“Are only the four orthogonal moves allowed, with no diagonals?”

Confirming this rules out sneaky diagonal shortcuts and fixes the move set.

“Can a cell be revisited within the same path?”

No — each path is simple, which is exactly what the visited marks enforce.

Output

“Should the paths come back in lexicographic order?”

This decides whether we sort at the end or order our moves to get sorting for free.

The ideal opening — say it like this

Before I code, a few quick checks.

The grid is n by n, and I return an empty list if either corner is blocked — correct?

Movement is the four orthogonal directions, no diagonals, and a cell cannot repeat within one path?

And the paths should be lexicographically ordered — I will try directions as D, L, R, U to handle that.

Key observations

1Aha

A path is a trail you lay down and pick back up

Standing on a cell, your only state is where you are and which cells your current trail already occupies. Mark a cell when you step on it, unmark it when you leave, and that same cell is free to appear in a completely different path later.

enter (r,c): mark visited -> try 4 moves -> unmark (r,c) before returning

2Aha

Prune before you step, not after

Check that the next cell is in-bounds, open (== 1), and unvisited before recursing into it. This kills dead branches at the door, so the search tree only ever holds partial trails that are still alive.

3Aha

Order the directions and sorting comes for free

If you always try moves in the order D, L, R, U — which is alphabetical — the first complete path you finish is the lexicographically smallest, and every path after it is larger. No final sort needed.

D < L < R < U   ->  recurse in that order  ->  results emerge pre-sorted

Brute force vs optimal

	Brute force	Optimal
Time	O(4^(n^2) · n^2)	O(4^(n^2))
Space	O(n^4)	O(n^2)
Visited state	copy the whole set each step	mark on enter, unmark on leave
Ordering	sort at the end	ordered moves, sorted for free

Both explore the same search tree; the optimal one just refuses to photocopy its notebook at every step. The full code for each is in the Approaches selector below.

Summary

Key takeaway

Backtracking is "choose, explore, un-choose." Carry a single shared record of the current trail, mark a cell on the way in and unmark it on the way out, and try directions alphabetically to get sorted output without sorting. This mark/unmark rhythm is the backbone of every grid-path, permutation, and N-Queens problem.

solve(r, c, path):
    if (r, c) is destination: record path; return
    mark (r, c) visited
    for (dr, dc, ch) in [D, L, R, U]:
        nr, nc = r + dr, c + dc
        if in bounds and mat[nr][nc] == 1 and not visited: solve(nr, nc, path + ch)
    unmark (r, c) visited