LeetCode 980: Unique Paths III Solution

Master LeetCode problem 980 (Unique Paths III), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

980. Unique Paths III

Hard

Array Backtracking Bit Manipulation Matrix

Problem Explanation

Explanation

To solve this problem, we can use backtracking to explore all possible paths from the starting square to the ending square while ensuring that we visit every non-obstacle square exactly once. We can keep track of the number of squares visited and compare it with the total number of non-obstacle squares to determine if a valid path has been found. We also need to handle cases where the path reaches the ending square without visiting all non-obstacle squares.

We start exploring paths from the starting square and move in all four directions (up, down, left, right) while updating the number of visited squares. Whenever we reach the ending square, we check if all non-obstacle squares have been visited. If so, we increment the count of valid paths.

Time complexity: O(4^(mn)), where m and n are the dimensions of the grid. Space complexity: O(mn) for the visited array and recursion stack.

Solution Code

class Solution {
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int count = 0;
    
    public int uniquePathsIII(int[][] grid) {
        int emptySquares = 0;
        int startX = 0, startY = 0;
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    emptySquares++;
                } else if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        dfs(grid, startX, startY, emptySquares);
        
        return count;
    }
    
    private void dfs(int[][] grid, int x, int y, int emptySquares) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) {
            return;
        }
        
        if (grid[x][y] == 2) {
            if (emptySquares == 0) {
                count++;
            }
            return;
        }
        
        if (grid[x][y] == 0) {
            emptySquares--;
        }
        
        grid[x][y] = -1; // mark as visited
        
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            dfs(grid, newX, newY, emptySquares);
        }
        
        grid[x][y] = 0; // backtrack
        emptySquares++;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 980 (Unique Paths III)?

This page provides optimized solutions for LeetCode problem 980 (Unique Paths III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 980 (Unique Paths III)?

The time complexity for LeetCode 980 (Unique Paths III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 980 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 980 in Java, C++, or Python.

Back to LeetCode Solutions