The O(n) Club: Unique Paths III and the Roomba That Never Misses a Spot

The O(n) Club: Unique Paths III and the Roomba That Never Misses a Spot

⚡ TL;DR

Pathfinding? Easy. Pathfinding without leaving a single square unvisited? You’d have an easier time keeping a toddler in clean clothes. The trick: Use backtracking DFS, track every step, only celebrate if you visit every empty (0) cell and the start (1)—ending at the target (2). If that smells like recursion with a side of bookkeeping, you’re not wrong. Sample Java vibe:

public int uniquePathsIII(int[][] grid) {
    // This is where dreams of non-repetitive walking go to die
}

🧠 How Devs Usually Mess This Up

Step 1: Ignore the “visit every square exactly once” rule, and just sprint from start to end. Result: disappointment.
Step 2: Forget to backtrack your ‘visited’ flags. Now you get double-counted paths or infinite loops to nowhere.
Step 3: Let the robot sweep the same tile twice—a.k.a. cheat mode, which this problem will swiftly punish.

🔍 What’s Actually Going On

Imagine you’re programming a Roomba with OCD: It must start from its dock (1), end at the charging station (2), and vacuum every ounce of dust (every 0)—once. Furniture (-1) is off-limits. Each step, mark the visited cell so you can’t retrace. If you finish having visited every eligible tile, cheer! If you finish early or loop twice, count exactly zero.
It’s state management at its finest, recursion at its sweatiest.

🛠️ PseudoCode

• Count all empty squares (0) + start (1); call this emptyCount.
• Find starting point (startX,startY).
• Define dfs(x, y, remain) to:
• Return if out-of-bounds, hitting -1 (furniture), or -2 (already visited in this path).
• If at (2): If remain==0, count as a valid path.
• Mark as visited (set to -2), recurse all four ways (up, down, left, right), reducing remain.
• Unmark on the way back (reset to 0 or whatever was there)—because recursion leaves no mess behind.
• Start recursion from start cell with emptyCount.
• Return total paths found.

💻 The Code

public class Solution {
    int result = 0;
    public int uniquePathsIII(int[][] grid) {
        int empty = 1;
        int startX = 0, startY = 0;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) empty++;
                if (grid[i][j] == 1) { startX = i; startY = j; }
            }
        }
        dfs(grid, startX, startY, empty);
        return result;
    }
    private void dfs(int[][] grid, int x, int y, int remain) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length
            || grid[x][y] == -1 || grid[x][y] == -2) return;
        if (grid[x][y] == 2) {
            if (remain == 0) result++;
            return;
        }
        int temp = grid[x][y];
        grid[x][y] = -2;
        dfs(grid, x+1, y, remain-1);
        dfs(grid, x-1, y, remain-1);
        dfs(grid, x, y+1, remain-1);
        dfs(grid, x, y-1, remain-1);
        grid[x][y] = temp;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Count the starting square, or every path is wrong. Devs miss this. A lot.
• If you forget to unmark on backtrack, you’ll block other valid routes. Recursion revenge is swift.
• DFS time explodes fast: O(4^N). This is fine for small grids; for bigger rooms, you’d need an army of Roombas or a lot more caffeine.
• StackOverflow is a literal threat here (the error, not the forum).
• If start or end are surrounded by walls, answer is zero—no amount of optimism fixes this.

🧠 Interviewer Brain-Tattoo

“Reaching the end? Child’s play. Cleaning every square—with no repeats? That’s interview-worthy.”