Unique Paths III

HardBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n integer grid where each cell is one of: - 1: the start cell (exactly one), - 2: the end cell (exactly one), - 0: an empty cell you may walk on, - -1: an obstacle you cannot enter. Moving one step up, down, left, or right at a time, count the walks from the start to the end that visit **every non-obstacle cell exactly once** (including the start and end). Return that count.

Examples

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Two snake-like walks cover all 11 walkable cells and finish on the 2.
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Four walks cover all 12 cells.
Input: grid = [[0,1],[2,0]]
Output: 0
Any walk that covers all four cells cannot finish on the 2.

Constraints

  • 1 <= m, n <= 20
  • 1 <= m * n <= 20
  • -1 <= grid[i][j] <= 2
  • There is exactly one start cell and one end cell.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems